Graph Algorithms: Dijkstra and Beyond

Why this matters in interviews

Shortest path problems show up constantly in coding interviews because they test more than one skill at once. You need to model the problem correctly, choose the right graph representation, and know which algorithm fits the constraints.

A common trap is reaching for Dijkstra everywhere just because it is the most famous shortest path algorithm. That works only when edge weights are non-negative. If the graph has negative edges, or if you need to detect negative cycles, you need something else. Interviewers like this topic because it reveals whether you understand the tradeoffs behind graph algorithms, not just the names.

In this post, you will learn how to recognize shortest path problems, how Dijkstra works, when it fails, and what to use instead.

Problem statement

You are given a weighted graph and asked to find the minimum cost path between nodes, or from one source to all nodes.

Typical variations include:

• Find the shortest path from node s to node t
• Find the shortest distance from a source to every node
• Handle directed or undirected graphs
• Deal with negative weights
• Detect whether a negative cycle exists

The main question is not just “how do I solve this?” It is also “which shortest path algorithm is valid here?”

Intuition: shortest path as repeated relaxation

Most shortest path algorithms are built on one idea: relaxation.

If you know the shortest distance to a node u, and there is an edge u -> v with weight w, then you can try improving the best known distance to v using:

dist[v] = min(dist[v], dist[u] + w)

This is called relaxing the edge.

If you relax edges in the right order, shortest path distances eventually stabilize.

Where Dijkstra fits

Dijkstra’s algorithm works when all edge weights are non-negative. It repeatedly picks the not-yet-finalized node with the smallest current distance, then relaxes its outgoing edges.

Why does this greedy choice work? Because with non-negative weights, once you have the smallest tentative distance among unprocessed nodes, no later path can improve it.

Where Dijkstra fails

If a graph contains a negative edge, a path that looks more expensive early may become cheaper later. That breaks the greedy assumption.

For those cases, Bellman-Ford is the standard fallback. It is slower, but it handles negative weights and can detect negative cycles.

Approach 1: Dijkstra’s algorithm

Use Dijkstra when:

• All edge weights are non-negative
• You need shortest path from one source
• You want efficiency on sparse graphs

Example 1: shortest path from one source

import heapq
from collections import defaultdict


def dijkstra(n, edges, source):
    graph = defaultdict(list)
    for u, v, w in edges:
        graph[u].append((v, w))
        # If the graph is undirected, also add:
        # graph[v].append((u, w))

    INF = float('inf')
    dist = [INF] * n
    dist[source] = 0
    pq = [(0, source)]

    while pq:
        cur_dist, u = heapq.heappop(pq)
        if cur_dist > dist[u]:
            continue

        for v, w in graph[u]:
            new_dist = cur_dist + w
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(pq, (new_dist, v))

    return dist

Walkthrough

Suppose we have this graph:

0 -> 1 (4)
0 -> 2 (1)
2 -> 1 (2)
1 -> 3 (1)
2 -> 3 (5)

Start from node 0:

1. dist = [0, inf, inf, inf]
2. Pop 0, relax neighbors:
   • dist[1] = 4
   • dist[2] = 1
3. Pop 2 next because it has the smallest tentative distance.
   • Improve 1 from 4 to 3
   • Set 3 = 6
4. Pop 1 with distance 3.
   • Improve 3 from 6 to 4
5. Pop 3.

Final distances:

[0, 3, 1, 4]

That is the shortest distance from node 0 to every node.

Why the priority queue matters

A plain BFS queue does not work for weighted graphs because the next node to explore is not necessarily the one with the smallest distance. The heap keeps the smallest tentative distance on top, which preserves Dijkstra’s greedy behavior.

Approach 2: Bellman-Ford for negative weights

Use Bellman-Ford when:

• Edge weights may be negative
• You need to detect negative cycles
• The graph is small enough for an O(VE) algorithm

Bellman-Ford relaxes every edge V - 1 times, because the shortest path can use at most V - 1 edges in a graph without negative cycles.

Example 2: Bellman-Ford implementation

def bellman_ford(n, edges, source):
    INF = float('inf')
    dist = [INF] * n
    dist[source] = 0

    # Relax all edges V-1 times
    for _ in range(n - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break

    # Detect negative cycle
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            return None  # Negative cycle detected

    return dist

Walkthrough

Consider:

0 -> 1 (1)
1 -> 2 (-1)
0 -> 2 (4)

From source 0:

• First pass:
  • dist[1] = 1
  • dist[2] = 4
  • then 1 -> 2 improves dist[2] to 0
• Second pass:
  • no further improvement

Result:

[0, 1, 0]

Dijkstra would not be safe here because of the negative edge 1 -> 2.

Approach 3: Detecting and reasoning about negative cycles

A negative cycle means you can keep looping and decrease the path cost forever. In interview terms, that often means the answer is undefined or should be reported specially.

Bellman-Ford detects this by doing one extra relaxation pass after the normal V - 1 passes. If any edge can still improve a distance, a negative cycle is reachable from the source.

Example 3: negative cycle detection

edges = [
    (0, 1, 1),
    (1, 2, -1),
    (2, 1, -1),
]

result = bellman_ford(3, edges, 0)
print(result)  # None

Here, 1 -> 2 -> 1 has total weight -2. Every extra cycle makes the path cheaper, so there is no meaningful shortest path.

How to choose the right algorithm

When you see a shortest path problem, ask these questions:

1. Are all weights non-negative?
   • Yes: Dijkstra is usually best.
   • No: consider Bellman-Ford.
2. Do you need to detect negative cycles?
   • Yes: Bellman-Ford.
3. Is the graph unweighted or all weights equal?
   • Use BFS instead.
4. Do you need all-pairs shortest paths?
   • Consider Floyd-Warshall for smaller graphs.

Complexity analysis

Here is a practical comparison of common shortest path approaches:

A good interview habit is to say the algorithm choice out loud and justify it based on constraints.

Common implementation details and pitfalls

1. Use adjacency lists for sparse graphs

Most interview graphs are sparse. An adjacency list is usually more memory-efficient than an adjacency matrix.

2. Skip stale heap entries in Dijkstra

The heap may contain multiple entries for the same node. Always check whether the popped distance is outdated:

if cur_dist > dist[u]:
    continue

Without this, your code still works, but it becomes slower and harder to reason about.

3. Initialize distances carefully

Use float('inf') for unknown distances. This makes comparison logic simple and avoids magic numbers.

4. Know the graph direction

Many bugs come from forgetting whether the graph is directed or undirected. In an undirected graph, each edge must be added in both directions.

5. Reconstruct the actual path when needed

Sometimes the interview asks for the path, not just the distance. Keep a parent array during relaxation.

import heapq
from collections import defaultdict


def dijkstra_path(n, edges, source, target):
    graph = defaultdict(list)
    for u, v, w in edges:
        graph[u].append((v, w))

    INF = float('inf')
    dist = [INF] * n
    parent = [-1] * n
    dist[source] = 0
    pq = [(0, source)]

    while pq:
        cur_dist, u = heapq.heappop(pq)
        if cur_dist > dist[u]:
            continue
        for v, w in graph[u]:
            nd = cur_dist + w
            if nd < dist[v]:
                dist[v] = nd
                parent[v] = u
                heapq.heappush(pq, (nd, v))

    if dist[target] == INF:
        return None, INF

    path = []
    cur = target
    while cur != -1:
        path.append(cur)
        cur = parent[cur]
    path.reverse()
    return path, dist[target]

This version is useful when the question asks for a route, such as navigation or dependency traversal.

Related problems you should connect this to

Shortest path algorithms rarely appear in isolation. They often connect to these patterns:

• BFS on graphs: shortest path in unweighted graphs
• Topological order on DAGs: shortest path in a directed acyclic graph can be solved faster than Dijkstra if you already have a DAG
• Union-Find: connectivity questions, though not shortest path
• A search*: Dijkstra with heuristics, useful in pathfinding problems
• Floyd-Warshall: all-pairs shortest path on small graphs

A strong interview answer often mentions the simplest valid approach first, then the more advanced option if constraints require it.

Key takeaways

• Dijkstra is the right tool for non-negative weighted graphs.
• Bellman-Ford handles negative edges and detects negative cycles.
• Relaxation is the core idea behind both algorithms.
• The graph constraints should drive your choice of algorithm.
• Always validate whether the problem is single-source, single-target, or all-pairs.

Final interview advice

If you are asked a shortest path problem, do not jump into code immediately. First, classify the graph:

• Weighted or unweighted?
• Directed or undirected?
• Any negative edges?
• Single source or all pairs?

That quick classification usually tells you the right solution.

If you want to see the distances, heap contents, and relaxation steps update live, I built an interactive version of this walkthrough at codebrew.ai — might help if you are a visual learner.

Practice these next

1. Network Delay Time — classic Dijkstra with a priority queue
2. Cheapest Flights Within K Stops — shortest path with an extra constraint
3. Path With Minimum Effort — Dijkstra on a grid
4. Bellman-Ford negative cycle detection — validate cycle handling
5. Shortest Path in a DAG — use topological ordering instead of Dijkstra