Shortest Paths: Dijkstra and Bellman-Ford
Find the cheapest route through a weighted graph. See why BFS stops being enough, how Dijkstra's greedy expansion with a priority queue works and why it needs non-negative weights, and how Bellman-Ford copes with negative edges.
When "fewest steps" is not "cheapest"
A navigation app does not want the route with the fewest turns. It wants the one that takes the least time, or the least distance, or the least toll. Each road segment has a cost, and the best route is the one whose costs add up to the smallest total. That is the single-source shortest path problem on a weighted graph: from one starting vertex, find the cheapest path to every other vertex.
BFS cannot do it. It counts edges, so it happily prefers a direct road of 100 km over a three-hop detour of 5 km each. You need an algorithm that understands weights. The most important one, and the model for many others, is Dijkstra's algorithm.
The basic move of every shortest-path algorithm: if going to v through u is cheaper than the best known distance to v (dist[u] + weight(u, v) < dist[v]), update dist[v] and remember u as its predecessor.
Dijkstra: expand the closest unfinished vertex
Imagine a fire starting at your source and spreading along roads at a speed proportional to the cost. The fire reaches the nearest vertex first, then the next nearest, always in order of true distance. Dijkstra simulates exactly that.
Keep a tentative distance for every vertex: zero for the source, infinity for the rest. Repeatedly pick the unfinished vertex with the smallest tentative distance. That distance is now final. Then relax every edge leaving it, in case the new vertex offers a shorter route to a neighbour.
Why is the first pick final? Any other route to that vertex would have to leave the finished region through some other unfinished vertex whose distance is at least as large, and since weights are not negative, adding more edges can only increase the cost. This is a greedy argument, and it is exactly where negative weights break everything: a later negative edge could undercut a distance you declared final.
The efficient way to repeatedly find the smallest tentative distance is a min-heap (priority queue). Push (distance, vertex) pairs. When you pop one whose distance is larger than the best known for that vertex, it is stale; skip it. Python's heapq has no decrease-key, so pushing duplicates and skipping stale ones is the standard trick.
3 2
A ------- B ------- C
\_______________/
10
start: dist[A]=0 dist[B]=inf dist[C]=inf
expand A: dist[B]=3 dist[C]=10
expand B: 3 + 2 = 5 < 10 -> dist[C]=5 (parent of C becomes B)
expand C: done1import heapq23graph = {4 "A": [("B", 7), ("C", 9), ("F", 14)],5 "B": [("A", 7), ("C", 10), ("D", 15)],6 "C": [("A", 9), ("B", 10), ("D", 11), ("F", 2)],7 "D": [("B", 15), ("C", 11), ("E", 6)],8 "E": [("D", 6), ("F", 9)],9 "F": [("A", 14), ("C", 2), ("E", 9)],10}1112def dijkstra(graph, source):13 dist = {v: float("inf") for v in graph}14 parent = {source: None}15 dist[source] = 016 heap = [(0, source)]17 while heap:18 d, u = heapq.heappop(heap)19 if d > dist[u]:20 continue # stale entry: a better route was found already21 for v, w in graph[u]:22 if d + w < dist[v]: # relaxation23 dist[v] = d + w24 parent[v] = u25 heapq.heappush(heap, (dist[v], v))26 return dist, parent2728def route(parent, target):29 path = []30 while target is not None:31 path.append(target)32 target = parent[target]33 return path[::-1]3435dist, parent = dijkstra(graph, "A")36for v in sorted(dist):37 print(v, dist[v], route(parent, v))
A 0 ['A'] B 7 ['A', 'B'] C 9 ['A', 'C'] D 20 ['A', 'C', 'D'] E 20 ['A', 'C', 'F', 'E'] F 11 ['A', 'C', 'F']
What it costs
With a binary heap and an adjacency list, each edge triggers at most one push, and each push or pop costs O(log V) (or O(log E), which is the same up to a constant). The total is O((V + E) log V). In a sparse graph that is close to linear, which is why Dijkstra scales to road networks with millions of vertices, usually with extra tricks on top.
Two cautions. First, Dijkstra needs non-negative weights. Second, if all weights are equal, BFS does the same job in O(V + E) with a plain queue. Dijkstra is, in effect, BFS with the queue replaced by a priority queue so that "closest" means cheapest rather than fewest edges.
Choosing a shortest-path algorithm
| Situation | Algorithm | Time |
|---|---|---|
| Unweighted graph | BFS | O(V + E) |
| Non-negative weights | Dijkstra with a binary heap | O((V + E) log V) |
| Negative weights, no negative cycles | Bellman-Ford | O(V * E) |
| Every pair of vertices, small graph | Floyd-Warshall | O(V^3) |
Negative weights and Bellman-Ford
Negative edge weights are not exotic: they model a refund, an energy gain on a downhill leg, or an exchange rate expressed through logarithms. They also defeat Dijkstra, as the next example demonstrates with a tiny graph where the greedy "this distance is final" claim is simply false.
Bellman-Ford makes no such claim. It relaxes every edge, V - 1 times in total. The reason V - 1 rounds suffice: a shortest path with no repeated vertices has at most V - 1 edges, and after round k the distances are correct for all paths using up to k edges. Run one more round, and if any distance still improves, there is a negative cycle reachable from the source, and "shortest" is meaningless because you can loop forever to drive the cost down. Bellman-Ford detects that; Dijkstra silently returns nonsense.
1import heapq23edges = [("S", "A", 2), ("S", "B", 3), ("B", "A", -2), ("A", "T", 1)]4vertices = ["S", "A", "B", "T"]56def bellman_ford(source):7 dist = {v: float("inf") for v in vertices}8 dist[source] = 09 for _ in range(len(vertices) - 1):10 for u, v, w in edges:11 if dist[u] + w < dist[v]:12 dist[v] = dist[u] + w13 negative_cycle = any(dist[u] + w < dist[v] for u, v, w in edges)14 return dist, negative_cycle1516def dijkstra(source):17 adj = {v: [] for v in vertices}18 for u, v, w in edges:19 adj[u].append((v, w))20 dist = {v: float("inf") for v in vertices}21 dist[source] = 022 done, heap = set(), [(0, source)]23 while heap:24 d, u = heapq.heappop(heap)25 if u in done:26 continue27 done.add(u) # declared final, never revisited28 for v, w in adj[u]:29 if v not in done and d + w < dist[v]:30 dist[v] = d + w31 heapq.heappush(heap, (dist[v], v))32 return dist3334print("bellman-ford:", bellman_ford("S"))35print("dijkstra: ", dijkstra("S"))3637edges.append(("T", "B", -1)) # B -> A -> T -> B now sums to -238print("with a negative cycle:", bellman_ford("S")[1])
bellman-ford: ({'S': 0, 'A': 1, 'B': 3, 'T': 2}, False)
dijkstra: {'S': 0, 'A': 2, 'B': 3, 'T': 3}
with a negative cycle: TrueMisconceptions and pitfalls
"The path with the fewest edges is the shortest." Only if all weights are equal. Otherwise two cheap edges beat one expensive one.
"Dijkstra works with negative weights if I am careful." It does not, because the finality argument fails. Use Bellman-Ford, or reweight the graph with Johnson's technique if you need many sources.
Skipping the stale-entry check. Without if d > dist[u]: continue the algorithm still returns correct distances, but it re-expands vertices with outdated distances and wastes time, possibly a great deal on dense graphs.
Storing only distances. To answer "which route?" you need the parent map. Walk it backwards from the target and reverse the result.
Using float("inf") arithmetic carelessly. Adding a weight to infinity is fine in Python; in languages with integer overflow, a "large number" sentinel plus a weight can wrap around to a negative.
A* is Dijkstra with a compass: it adds a heuristic estimate of the remaining distance to the priority, so the search is pulled toward the goal. Game and map software use it when you only need one target, not all of them.
Check your understanding
These questions test the reasoning behind the algorithm.
Roads: A to C direct costs 10; A to B costs 3 and B to C costs 2. BFS and Dijkstra are asked for the route A to C. How do they differ?
Quick Syntax & Reference Sheet
| Concept / Rule | Syntax / Usage |
|---|---|
| Relaxation | if dist[u] + w < dist[v]:
dist[v] = dist[u] + w; parent[v] = u |
| Dijkstra loop | d, u = heappop(heap)
if d > dist[u]: continue
for v, w in graph[u]: relax and heappush |
| Bellman-Ford | repeat V-1 times: relax every edge; one extra pass detects negative cycles |
| Rebuild route | walk parent[] from target to source, then reverse |
Common Pitfalls & Developer Mistakes
Running Dijkstra on a graph with negative edges
Why it happens: Settled distances can be undercut later, so the result may be wrong with no error.
Pushing to the heap without comparing against the current best
Why it happens: You flood the heap with useless entries and may reprocess vertices.
Forgetting the parent map
Why it happens: You know the cost but not the route.