Shortest paths
One question about the weights picks between BFS, Dijkstra, Bellman-Ford and Floyd-Warshall — with the arithmetic that rules three of them out.
Four algorithms answer "what is the shortest path", and one question separates them: what do the weights look like? Everything else — the heap, the relaxation rounds, the loop order — follows from the answer. Get the question right and the algorithm is forced; get it wrong and you write a correct implementation of the wrong thing.
The decision table
| Weights | Algorithm | Cost | Use it when |
|---|---|---|---|
| None (all edges cost 1) | BFS | O(V + E) | Any unweighted graph or grid |
| Non-negative | Dijkstra with a heap | O(E log V) | The default weighted case |
| Any, including negative | Bellman-Ford | O(V·E) | Negative edges, or you must detect a negative cycle |
| Any, all pairs | Floyd-Warshall | O(V³) | Every pair needed and V is small |
Now make it concrete. Take V = 10⁵ nodes and E = 2 × 10⁵ edges, at roughly 10⁸ simple operations per second:
- BFS: V + E = 3 × 10⁵ steps. Instant.
- Dijkstra: E log V ≈ 2 × 10⁵ × 17 ≈ 3.4 × 10⁶ elementary steps — about 2 × 10⁵ heap operations at ~17 comparisons each. Instant.
- Bellman-Ford: V · E = 10⁵ × 2 × 10⁵ = 2 × 10¹⁰ relaxations, about 200 seconds. Not viable. Bellman-Ford lives at V in the hundreds — at V = 500 and E = 2,000 it is 10⁶ relaxations, which is nothing.
- Floyd-Warshall: V³ = 10¹⁵. Absurd here. At V = 500 it is 1.25 × 10⁸, about a second; at V = 1,000 it is 10⁹ and marginal. Treat V ≤ 500 as the ceiling, matching the constraint table in complexity by counting.
The constraint in the problem usually names the algorithm before you have had an idea. V ≤ 500 with all-pairs asked for is Floyd-Warshall. V = 10⁵ with weights is Dijkstra. No weights at all is BFS, and reaching for a heap there is wasted work.
BFS is Dijkstra with every weight 1
When all edges cost the same, the queue is already in non-decreasing distance order, so a priority queue would sort something that is sorted. That is the whole reason BFS gets shortest paths for free, worked through in BFS and DFS. Keep this link in mind: it tells you that Dijkstra is the generalisation you pay a log factor for, and that you should only pay it when the weights differ.
Dijkstra, and the assumption a negative edge breaks
Dijkstra keeps tentative distances in a heap and repeatedly finalises the smallest one:
import heapq
def dijkstra(graph, source, n):
dist = [float('inf')] * n
dist[source] = 0
heap = [(0, source)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue # stale entry, already improved
for v, w in graph[u]:
nd = d + w
if nd < dist[v]:
dist[v] = nd
heapq.heappush(heap, (nd, v))
return dist
The if d > dist[u]: continue line is lazy deletion. Python's heap has no
decrease-key, so an improved distance is pushed as a new entry and the outdated
one is skipped when it surfaces. The heap holds up to E entries, which is where
O(E log V) comes from.
Correctness rests on one sentence: when the smallest tentative distance d is popped, no shorter route to that node can exist, because every alternative route leaves the settled set through some frontier node already at distance ≥ d and then adds edges that cannot lower the total. The last clause is the assumption, and a negative edge deletes it.
Three nodes are enough to see it. S→A costs 5, S→B costs 6, B→A costs −4, so the true distance to A is 6 − 4 = 2. Dijkstra pops A at 5 and the guarantee declares it final. Any implementation that acts on that — recording each node's answer at pop time, or refusing to relax out of a settled node — returns 5.
The version above does not act on it, and that is the more dangerous failure. When B relaxes the edge it pushes A again at 2 and returns the right answer on this graph. The heap has quietly become a work queue for repeated relaxation: nodes are popped more than once, the O(E log V) bound no longer holds, and on a graph with a reachable negative cycle the loop never terminates. Correct on the three-node example, unbounded on the real input, is the worst thing to ship.
The rule is not that Dijkstra usually copes. It is: one negative edge, use Bellman-Ford.
Bellman-Ford
Relax every edge, V − 1 times:
def bellman_ford(edges, n, source):
dist = [float('inf')] * n
dist[source] = 0
for _ in range(n - 1):
changed = False
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
changed = True
if not changed:
break # settled early
for u, v, w in edges:
if dist[u] + w < dist[v]:
return None # a negative cycle is reachable
return dist
Why V − 1 rounds: any shortest path visits each node at most once, so it has at most V − 1 edges, and after round k every shortest path of k edges is correct. Induction does the rest.
The last loop is the reason to keep Bellman-Ford in the toolbox even when Dijkstra would be faster. After V − 1 rounds nothing can improve — unless a negative cycle is reachable, in which case going round it once more lowers the total again, forever. One extra pass that still improves something is proof of a negative cycle. Dijkstra cannot report this at all.
Floyd-Warshall and the k loop
All pairs, V³ time, V² space, and seven lines:
def floyd_warshall(dist, n): # dist[i][j] = weight, inf if no edge
for k in range(n): # k MUST be the outer loop
for i in range(n):
for j in range(n):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
The k loop is the induction variable, not just another index. After iteration k
finishes, dist[i][j] is the best path from i to j using only the first k + 1
nodes as intermediates. Each new k asks one question of every pair: does routing
through k beat what you have? Put k innermost and you consult dist[i][k]
before k's own row has been settled for the intermediates it needs, and the
table fills with values that are not shortest paths for any set of allowed
intermediates.
Two setup details do most of the damage in practice. Initialise non-edges to
float('inf'), not 0 — a zero reads as a free edge and every path routes
through phantom links. And initialise dist[i][i] = 0. A negative value on the
diagonal after the run means i sits on a negative cycle.
In an interview
Ask about the weights before proposing anything, out loud: "are edge weights all equal? Can any be negative?" Two sentences, and the algorithm follows. Then give the number that rules the others out — "V is 10⁵ so Bellman-Ford is 2 × 10¹⁰ relaxations, which is minutes; Dijkstra is 2 × 10⁵ heap operations, about 3.4 × 10⁶ elementary steps."
The mistake that loses points: running Dijkstra on a graph with negative edges and defending it with "it passed the examples". State the assumption first, and if negatives are possible say so and switch — the interviewer is usually holding the three-node counterexample.
Check yourself
V = 400, and you need the distance between every pair. Which algorithm, and what does it cost?
Floyd-Warshall: 400³ = 6.4 × 10⁷ operations, well under a second, in seven lines. Running Dijkstra from all 400 sources also works and is more code for no gain at this size.
S→A costs 5, S→B costs 6, B→A costs −4. What does Dijkstra's guarantee claim about A, and what actually happens?
The guarantee says A is final the moment it is popped at 5; the true distance is 2 via B. An implementation that records the answer at pop time returns 5. The lazy-deletion version re-pushes A and returns 2 — right here, but it is no longer bounded by O(E log V) and it will not terminate at all if a negative cycle is reachable. Either way, a negative edge means Bellman-Ford.
After V − 1 Bellman-Ford rounds, one more pass still improves a distance. What does that prove, and why does one pass suffice?
A negative cycle is reachable from the source. Any genuine shortest path has at most V − 1 edges, so V − 1 rounds settle all of them; a further improvement can only come from going around a cycle whose total weight is negative.