Shortest Paths

When to use a shortest path algorithm

Use a shortest path algorithm when you need:

• The cheapest route between places where edges have different costs: road distance, flight price, network latency.
• The cheapest route when some costs are negative, such as a trade that earns money or a refund: use Bellman-Ford.
• The distance between every pair of vertices in a small graph, for example a table of travel times between 300 depots: use Floyd-Warshall.
• To detect a negative cycle, such as a currency loop that makes money from nothing (arbitrage): Bellman-Ford or Floyd-Warshall.

Use something else when:

• Every edge costs the same (or the graph has no weights): plain BFS finds the fewest edges in O(V + E).
• All weights are zero or one: use 0-1 BFS with a double-ended queue.
• The graph is a DAG (no cycles): relax the edges in topological order for O(V + E), even with negative weights.
• You need a path to one target on a huge map with a good distance estimate: use A* instead of searching in every direction.

Do not write your own graph library in production. Use a tested one (see the real-world section). Writing these from scratch is for learning and interviews.

How shortest path algorithms work

All three algorithms rest on one operation, relaxing an edge. If you know the best distance to u, and there is an edge u → v of weight w, then going through u might beat the best known distance to v:

Relax u → v: if dist[u] + w < dist[v], set dist[v] = dist[u] + w.

They differ in the order they relax edges, which decides what they can handle. A priority queue (a min-heap) is a structure that always hands back the item with the smallest key, and Dijkstra uses one to find the closest unfinished vertex quickly.

• Dijkstra always finalises the closest unfinished vertex next and relaxes its outgoing edges. Because nothing can be closer than the closest, that vertex's distance can never improve again. This is only true when no edge is negative.
• Bellman-Ford does not trust any order. It relaxes every edge, V - 1 times. A shortest path has at most V - 1 edges, so after that many rounds every distance is correct. One extra round that still improves something proves a negative cycle.
• Floyd-Warshall answers all pairs. It allows one more vertex k at a time as a middle stop and asks, for every pair, "is i → k → j shorter than the best so far?"

Try it

Choose an algorithm and a graph. The graph has four vertices A, B, C, D and starts from A.

Things to try:

• Run Dijkstra on All weights positive. It finalises A, C, B, D and the distances are 0, 3, 2, 8 (B costs 3 through C, because 2 + 1 beats 4).
• Run Dijkstra on One negative edge. B is finalised at 2, then the edge C → B (weight -2) would give 1, but Dijkstra ignores it. The distances are wrong. Run Bellman-Ford on the same graph and it gets A to B right: 1.
• Run Bellman-Ford on A negative cycle. It reports the cycle. Then run Floyd-Warshall on the same graph and look for a negative number on the diagonal.

Shortest path operations: relax, pick the closest, repeat

Dijkstra. Keep a priority queue of unfinished vertices keyed by distance.

1. Set every distance to infinity, except the start, which is 0.
2. Take the unfinished vertex with the smallest distance and mark it final.
3. Relax every edge leaving it. Repeat from step 2 until the queue is empty.

Bellman-Ford.

1. Set every distance to infinity, except the start.
2. Repeat V - 1 times: relax every edge. Stop early if a whole round changes nothing.
3. Do one more round. If any edge still improves, a negative cycle is reachable from the start.

Floyd-Warshall. Keep a matrix d[i][j] of best distances, starting with the direct edges. For k from 1 to V, for every i and j, set d[i][j] = min(d[i][j], d[i][k] + d[k][j]). A negative value on the diagonal means a negative cycle.

Dijkstra needs non-negative weights, and that is the question interviewers ask. After a vertex is finalised, a negative edge could still make it cheaper, so its answer would be wrong. Bellman-Ford pays more to avoid that assumption.

Dijkstra in code, with the path. Keep a prev array: each time a relaxation succeeds, record which vertex it came from. To print the route, walk prev back from the target and reverse.

import heapq

def dijkstra(n, adj, src=0):
    # adj[u] is a list of (v, weight) pairs; all weights must be >= 0.
    INF = float("inf")
    dist = [INF] * n
    prev = [None] * n
    dist[src] = 0
    heap = [(0, src)]                       # (distance, vertex)
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:                     # stale entry: a better one was already processed
            continue
        for v, w in adj[u]:
            if d + w < dist[v]:             # relax u -> v
                dist[v] = d + w
                prev[v] = u
                heapq.heappush(heap, (dist[v], v))
    return dist, prev

def path_to(prev, target):
    path = []
    while target is not None:
        path.append(target)
        target = prev[target]
    return path[::-1]                       # a path of just [target] means no route if target != src

Worked trace on the "All weights positive" graph (edges A→B 4, A→C 2, C→B 1, B→D 5, C→D 8):

Walking prev back from D gives D, B, C, A, so the path is A → C → B → D with cost 8. Bellman-Ford and Floyd-Warshall can record the predecessor in the same way when a relaxation succeeds.

Edge cases to check.

• Unreachable vertices keep distance ∞. Treat ∞ as "no route", and never add a weight to ∞ without checking (the Bellman-Ford code tests dist[u] != INF for this reason).
• Parallel edges: keep the cheapest (Floyd-Warshall starts with min of the duplicates).
• Stale heap entries: the heap may hold several entries for one vertex; skip any whose distance is larger than the current best, as the code above does.
• Negative cycle in Floyd-Warshall: values on the cycle can keep shrinking and grow very negative, so check the diagonal for negatives after the run.
• Zero-weight edges are fine for Dijkstra. Only negative weights break it.

Shortest path time complexity

V is the number of vertices and E the number of edges. Space is the extra memory beyond the graph itself; storing the graph as an adjacency list takes O(V + E) for every algorithm. Dijkstra's heap version is far faster than Bellman-Ford on large sparse graphs, which is why it is the default whenever weights are non-negative. Floyd-Warshall's cube is fine up to a few hundred vertices.

Shortest path algorithms vs other approaches

Here V is vertices and E edges. Dijkstra wins on large graphs with non-negative weights. Bellman-Ford wins when negative edges or cycle detection matter, and Floyd-Warshall wins for small all-pairs problems.

How to explain shortest paths in an interview

• Start with the question "are there negative weights?" It decides everything: no negatives means Dijkstra, negatives means Bellman-Ford, and unweighted means BFS.
• Describe relaxation in one sentence, and say that Dijkstra's greedy choice is valid only because no later path can be cheaper than the closest vertex.
• Give complexity in V and E: Dijkstra O((V + E) log V), Bellman-Ford O(V × E), Floyd-Warshall O(V³).
• Mention negative cycles: shortest paths are undefined, and Bellman-Ford's extra round finds them. In a currency problem, take the logarithm of rates to turn products into sums.