Shortest paths with Dijkstra and Bellman-Ford in Python

Why it matters

A navigation app that picks the fastest route, a network router that chooses the cheapest path for a packet, and a game that moves a character around obstacles all solve one problem. They find the cheapest route from a start to a goal, where each road has a cost. The costs might be kilometres, minutes, bandwidth or money. Lesson 1 found shortest paths by counting hops, which gives the wrong answer as soon as the roads have different costs. This lesson fixes that with Dijkstra's algorithm, the standard method for weighted graphs without negative roads. It then shows Bellman-Ford, for the case where a road can have a negative cost.

Why counting hops is not enough

Take three towns, A, B and C. The direct road from A to C costs 10 minutes. The road from A to B costs 2 minutes, and the road from B to C costs 3 minutes. BFS from A reaches C in one hop, so it would pick the direct road, which takes 10 minutes. The route through B has two hops and takes only 5 minutes. For a driver, the two-hop route is the better answer, and BFS cannot see it, because BFS does not look at costs at all.

So the question changes. We are no longer looking for the path with the fewest edges. We want the path whose total weight is smallest. The weight of a path is the sum of the weights of its edges. The shortest path is the path with the smallest total weight.

Two words help here. A weight is the number on an edge: its cost, length or time. A distance from a start vertex to another vertex is the smallest total weight of any path between them. A distance belongs to the pair of vertices, not to one route, so the answer is one number per vertex.

The idea: water spreading through pipes

Picture the graph as a network of pipes. Each pipe has a length that is its weight. Pour water in at the start. The water flows through the pipes at a steady speed, and it reaches each junction after the time it takes to travel along the shortest pipe route to that junction. If you could watch the water, the junctions would get wet one by one, in order of their distance from the start.

Dijkstra's algorithm copies that picture. It always finishes the closest vertex that has not been finished yet. Once a vertex is finished, its distance is final, and it never changes again. The algorithm then looks at the roads leaving that vertex and checks whether they give a shorter route to any neighbour.

The check has a name: relaxing an edge. Suppose the best known distance to u is d, the edge from u to v has weight w, and the best known distance to v is dv. If d + w is less than dv, you found a shorter way to v. You write the new distance, d + w, into dv. Relaxing is the only operation the algorithm performs on distances.

A small case: vertex 1 starts at distance 4, the cost of the direct road from vertex 0. When the algorithm finishes vertex 2 at distance 1, it looks at the road from 2 to 1 with weight 2. The route 0, 2, 1 costs 1 + 2 = 3, which is less than 4, so the distance of vertex 1 drops to 3. That drop is one relaxation.

Dijkstra's algorithm step by step

Dijkstra's algorithm has a clear recipe:

1. Set the distance to the start to 0 and the distance to every other vertex to infinity.
2. Put (0, start) into a priority queue, ordered by distance, smallest first.
3. Take out the pair with the smallest distance. Call its vertex u and its distance d.
4. If d is larger than the best known distance to u, this pair is out of date. Skip it.
5. For each edge from u to v with weight w, relax it. If d + w improves the distance to v, update the distance and push (d + w, v) into the queue.
6. Repeat from step 3 until the queue is empty.

The priority queue is the new tool here. The standard library has queue.PriorityQueue, but it is built for code that runs several threads, so graph code normally uses heapq. The heapq module gives you a min-heap on a plain list. A min-heap keeps its smallest item at the front, so heapq.heappop always returns the smallest item. Each item is a tuple, and tuples compare item by item. So the entries (distance, vertex) come out ordered by distance, and no comparator function is needed. Put the distance first in each tuple.

The heaps lesson earlier in this track explained how a heap works. Here the heap holds pairs of distance and vertex. Taking out the front gives you the closest unfinished vertex, which is exactly what the water analogy needs.

Why does it work? Take the first vertex that comes out of the queue with its final distance. Any other route to it would have to leave the start through some unfinished vertex, and every unfinished vertex is at least as far away as this one. Since no edge has a negative weight, adding more roads cannot make the total smaller. So the route found first is the shortest. This argument needs every weight to be zero or more. That is the one rule Dijkstra cannot break, and it returns in the Bellman-Ford section.

The complexity with a binary heap is O((V + E) log V). Each edge may cause one heap push, and each push or pop costs O(log V). Space is O(V + E).

Stale entries and why they are fine

Step 4 of the recipe is easy to skip, and it matters. A vertex can be pushed into the queue several times, once for each time its distance improved. An old entry for the vertex still sits in the queue with a larger distance. When that entry comes out, the vertex already has a better distance, so the entry is stale. Processing it again would not change the answer, but it wastes time. The check if d > dist[u]: continue throws it away.

Worked example, step by step

Use the same four-vertex graph as Program 1 below: edges 0 to 1 with weight 4, 0 to 2 with weight 1, 2 to 1 with weight 2, 1 to 3 with weight 1, and 2 to 3 with weight 5. The graph is undirected, so every edge works both ways.

The distances start as [0, inf, inf, inf], and the queue holds (0, 0), written as (distance, vertex).

Pop (0, 0). Its edges go to 1 with weight 4, and to 2 with weight 1. Vertex 1 gets 4 and (4, 1) enters the queue. Vertex 2 gets 1 and (1, 2) enters the queue. Distances are [0, 4, 1, inf]. The queue holds (1, 2) and (4, 1).

Pop (1, 2), the smallest. Its edges go to 0 (weight 1), 1 (weight 2) and 3 (weight 5). Vertex 0 gives 2, which is not less than 0, so nothing happens. Vertex 1 gives 1 + 2 = 3, which is less than 4, so it improves and (3, 1) enters the queue. Vertex 3 gets 1 + 5 = 6 and (6, 3) enters the queue. Distances are [0, 3, 1, 6]. The queue holds (3, 1), (4, 1) and (6, 3).

Pop (3, 1). Its edges go to 0 (weight 4, gives 7, no change), 2 (weight 2, gives 5, no change) and 3 (weight 1, gives 4, which is less than 6). Vertex 3 improves to 4 and (4, 3) enters the queue. Distances are [0, 3, 1, 4].

Pop (4, 1). This is stale, because dist[1] is 3 and 4 is larger. Skip it.

Pop (4, 3). Its edges go to 1 and 2, and neither improves. The queue now holds (6, 3), also stale. Skip it as well.

The queue is empty. The final distances are [0, 3, 1, 4]. Vertex 3 is reached by the route 0, 2, 1, 3, costing 1 + 2 + 1 = 4.

Watch the heap in the visualizer below. The front of the heap is always the closest entry, and stale entries stay behind until they come out and are skipped.

Program 1: distances from one start

Here is Dijkstra as a complete program. It runs the algorithm from vertex 0 and prints the distance to every vertex. The graph is written into the program, so the program needs no input. To try another graph, change the edges list and n.

Python integers have no size limit, so the distances never overflow. The distance to an unreachable vertex is math.inf, Python's float infinity. Adding a number to math.inf gives math.inf again, so the program can add weights to an unreached vertex without any harm.

Expected output:

distances: [0, 3, 1, 4]

The stale check is the line if d > dist[u]: continue. Here d is the distance stored in the popped tuple, and dist[u] is the best distance known so far. A smaller dist[u] means the popped entry is old.

Program 2: the cheapest route itself

The distances tell you how far, but a navigation app must show the route. The parent-array trick from lesson 1 works here too. Whenever a relaxation improves dist[v], record parent[v] = u. When the algorithm finishes, walk back from the goal to the start by following parents, and reverse the list.

The function returns None when the goal cannot be reached. Test this before you walk the parents. If the goal is unreachable, its parent is -1, and the walk would print just the goal, which looks like a route but is wrong.

Expected output:

cost: 4
path: 0 2 1 3

The line " ".join(str(v) for v in path) builds the text 0 2 1 3. The inner expression is a generator expression. It turns each vertex number into text, and join puts a space between the pieces.

Check the parent chain by hand. Vertex 3 was last improved from vertex 1, so parent[3] is 1. Vertex 1 was improved from vertex 2, so parent[1] is 2. Vertex 2 was reached from 0, so parent[2] is 0, and the start has -1. Reading the chain backwards gives 0, 2, 1, 3, with cost 1 + 2 + 1 = 4.

Bellman-Ford: when an edge is negative

Dijkstra needs every weight to be zero or more. A negative weight is a road where you gain something, such as a refund, a discount or a stored-energy trip. The problem is that Dijkstra assumes a finished vertex can never be improved. A negative edge can break that. A route that looks expensive at first can become cheap after a refund, and by then Dijkstra has already finished the vertex.

Bellman-Ford is the slower, safer method. Its idea is simple. Relax every edge, in any order. Repeat that whole pass V - 1 times. The reason is that any shortest path has at most V - 1 edges, because a shortest path in a graph without a negative cycle never repeats a vertex. After pass k, every shortest path with up to k edges has been found. After V - 1 passes, all of them are found.

The program below stores the edges as (u, v, w) tuples. The edges are directed: (u, v, w) means a one-way road from u to v. A negative cycle is a loop of roads whose total weight is negative. Walking round it again and again lowers the cost each time. If a shortest path cannot be found because such a loop exists, the program says so.

The program runs two graphs. Graph a has one negative edge and no loop. Graph b has a loop 1 to 2 to 1 with total weight -2.

Expected output:

graph a distances: [0, 4, 1]
graph b negative cycle

Trace graph a. Pass 1 relaxes the edges in input order. The edge 0 to 1 gives vertex 1 the value 4. The edge 0 to 2 gives vertex 2 the value 5. The edge 1 to 2 is then checked with the value 4 for vertex 1, giving 4 - 3 = 1, which is less than 5, so vertex 2 drops to 1. The second pass finds nothing new. Vertex 2 has distance 1, which is the true shortest distance. It is reached through vertex 1 by a negative edge. Dijkstra gets this graph right, because it finishes vertex 1 before vertex 2. Mistake 3 shows a case where it does not.

With three vertices, the loop runs for passes 1 and 2, which is V - 1 passes. The final check does one more pass and looks for any edge that still improves.

The program does not need a check for unreached vertices. A vertex nothing has reached yet has the value math.inf. Adding a negative weight to math.inf still gives math.inf, so the comparison is false and the vertex is not changed. In a language with integer distances, a large number standing in for infinity can overflow when a weight is added, so it needs a guard. Python does not need one here.

Why the passes have to repeat

One pass fixes a path only as far as the order of the edges allows. Take a path of three edges, 0 to 1, 1 to 2 and 2 to 3, and list the edges in the reverse order: first 2 to 3 with weight 1, then 1 to 2 with weight -5, then 0 to 1 with weight 2. Start at vertex 0 with four vertices.

The path to vertex 3 has three edges, and each pass fixed one more of them. The edge from 2 to 3 came first in the list, so its information could only arrive in the next pass. A fourth pass would change nothing.

This is why the loop runs V - 1 times and not once. Each pass guarantees one more edge of every shortest path is correct, and a shortest path has at most V - 1 edges.

Now the negative cycle. In graph b, the loop 1 to 2 to 1 has total weight -1 + -1 = -2. Walking round it lowers the cost every time, so no shortest path exists. The extra pass finds that vertex 1 can still be improved after V - 1 passes. Bellman-Ford reports that case. Dijkstra would give an answer, and the answer could be wrong without any error message.

The time is O(V * E), because V - 1 passes each scan E edges. For a graph with 10,000 vertices and 100,000 edges, that is about a billion edge checks, which is far slower than Dijkstra. Use Bellman-Ford only when negative weights are possible.

Program 3: the cheapest path through a grid

Grids are graphs, and they often come with costs. Imagine a field where each cell has a difficulty from 1 to 9, and you want the cheapest walk from the top-left corner to the bottom-right corner. Entering a cell costs its digit. This is shortest paths on a grid with weights, and Dijkstra handles it directly.

The grid is a list of strings, one string per row. Each character is a digit. The function int(ch) turns a character such as "7" into the number 7. Without that conversion, the program fails with an error, which is one of the mistakes below.

Expected output:

cheapest: 11

The cheapest walk goes right two cells along the first row, down to row 1 in the third column, right one cell, then down to the corner. Those cells are (0,1), (0,2), (1,2), (1,3) and (2,3), with costs 1, 3, 4, 2 and 1. The total is 11. The walk through (1,0) costs more, because the cell after it is a 5 or an 8. Dijkstra finds the cheapest walk without trying every walk.

The cost of a cell is paid when you enter it, not when you leave it. The start cell costs nothing, because you are already standing on it. This is a common convention, and a problem may use a different one, so read the statement.

The steps list holds the four directions as (row change, column change) pairs. The bounds check 0 <= nr < rows is a chained comparison. Python reads it as two comparisons joined by and.

The comparison

The three algorithms in this module that answer shortest-path questions are easy to mix up. This table is the one to remember.

Which one to pick depends on the weights, not on the size. If every edge has the same cost, BFS is correct and faster. If some costs are negative, Dijkstra can be wrong, so use Bellman-Ford. If all costs are zero or more and the graph is big, use Dijkstra.

What happens inside heapq

heapq stores the heap in a plain Python list. The list is not sorted. It is arranged so that each item is no larger than the two items below it. The item at index 0 is always the smallest. When you push, heapq puts the new item at the end and moves it up until the order holds again. When you pop, it takes item 0 off, moves the last item to the top, and moves it down. Both moves take a number of steps about equal to log2 of the number of items. With a million items that is around 20 steps.

If you print the heap list, the numbers look unordered. That is normal. Use sorted(heap) to read the items in order, as the visualizer does.

The heap is the reason Dijkstra costs log V per operation and not V. Replacing the heap with an unsorted list would give each pop a full scan, and the algorithm would slow down to O(V^2). For a graph with 10,000 vertices that is 100 million steps, against about 130,000 with a heap.

Common mistakes and the messages they produce

Mistake 1: putting an item that cannot be compared into a heap. Tuples compare item by item. If two tuples have the same first item, Python compares the second items. A dict cannot be compared with <, so this fails:

import heapq
 
heap = []
heapq.heappush(heap, (0, {"a": 1}))
heapq.heappush(heap, (0, {"b": 2}))

Python ends the error message with this line:

TypeError: '<' not supported between instances of 'dict' and 'dict'

The cure is to keep the heap items small and comparable. Put the distance first and the vertex number second, as the programs above do. Store any extra data in a separate list, and push only its index.

Mistake 2: using None as infinity. If the distances start as None, the comparison in the relaxation fails as soon as it reaches a vertex with no value yet:

dist = [0, None, None]
if 1 < dist[1]:
    print("shorter")

The output is this error line:

TypeError: '<' not supported between instances of 'int' and 'NoneType'

Use math.inf. It compares correctly with every number, and adding a weight to it gives math.inf.

Mistake 3: negative weights in Dijkstra. The algorithm trusts each vertex once it is finished, so a negative road can leave a wrong distance behind. Here is the directed graph with edges 0 to 1 (weight 1), 0 to 2 (weight 5) and 2 to 1 (weight -10). A version that marks a vertex as finished when it is popped, and never looks at it again, prints 1 for vertex 1. The cheapest route is 0, 2, 1, which costs -5. The program runs without an error and prints a number, and nothing tells you it is wrong. Check the weights before choosing the algorithm, and if any are negative, use Bellman-Ford.

Mistake 4: leaving out the stale check. Without if d > dist[u]: continue, the answers are still right, but each vertex is expanded once per queue entry. On a graph with many roads, this can slow the program down a lot. Add the check, and test on a graph with many parallel roads.

Mistake 5: an unreachable goal. If the goal has no route, its distance is still math.inf. Printing it gives inf, which can be mistaken for a real answer. Check for it before you print, as Program 2 does. For this graph, with vertex 3 cut off from the rest, the output is:

inf

Mistake 6: forgetting the reverse edge. A two-way road must be added in both directions. For a one-way road, add it once. Check which kind the problem describes, the same warning as lesson 1.

Mistake 7: a digit read as text. The character "1" is a string, not the number 1. Adding it to a number fails:

total = 0
total = total + "1"

The error line is:

TypeError: unsupported operand type(s) for +: 'int' and 'str'

Convert the character with int(ch) first, as the grid program does.

Debugging walkthrough

Suppose Dijkstra prints a distance that is too large for one vertex. Here is how to find the cause.

First, check the edges. Print the list of edges as the program stores them. A common slip is putting an edge in only one direction, or swapping the two vertex numbers.

Second, check the first pop. It must be the start with distance 0. If the queue starts with the wrong vertex, the first heapq.heappush is wrong.

Third, print each pop with its distance, and print each relaxation that succeeds. Compare the sequence with the worked example by hand. The first place where the program differs from your trace is the bug.

Fourth, check for negative weights. If the program is right on the positive examples and wrong on the one with a discount, the negative weight is the cause, so Dijkstra is the wrong choice. Switch to Bellman-Ford and see whether the answer changes.

Fifth, check the stale check. If the output is right but the program is slow, print the size of the heap at the end. A heap far larger than the number of edges points to a missing stale check or an edge added more than once.

Variations and edge cases

Single source versus all pairs. Dijkstra gives the distances from one start. For all pairs, you run it from every vertex, which costs O(V * (V + E) log V). For that problem, the Floyd-Warshall method is often used on small graphs, and it is taught later in this module, in lesson 16.

Early exit. If you only need the distance to one goal, stop the loop as soon as the goal is popped with a current distance. Its distance is final at that moment.

Zero-weight edges. Dijkstra handles zero weights correctly. A zero-weight edge does not make a vertex finish too early, because the argument needs only non-negative weights.

Ties. Two routes can have the same total. The program keeps the first one it found, and the distance is the same either way. A problem that asks for a particular route may need a tie-breaking rule. Tuples already break ties by the second item, which is the vertex number.

Edge cases to test. A start that is the goal (distance 0), an unreachable goal, a graph with one vertex, a graph where the cheapest route has more hops than a direct but expensive road, and a graph with a negative edge that Dijkstra would get wrong.

Interview questions this lesson answers

"Find the cheapest route between two cities with non-negative road costs." Dijkstra with a min-heap. O((V + E) log V) time, O(V + E) space.

"Why does BFS not work for weighted roads?" BFS counts edges and treats each one as cost 1. A route with fewer edges can cost more.

"What if a road has a negative cost?" Dijkstra can give a wrong answer, because it assumes a finished vertex can never be improved. Use Bellman-Ford, which relaxes every edge V - 1 times.

"Detect whether a graph has a negative cycle." Run Bellman-Ford and do one more pass. If any edge still relaxes, a negative cycle is reachable.

"Print the cheapest route, not just its cost." Keep a parent array in the relaxation and walk back from the goal. Check reachability before you walk.

Real-world uses

Navigation apps run Dijkstra or a faster variant on road networks with millions of nodes, using extra information about the direction of the goal to skip most of the graph. Internet routing protocols such as OSPF run Dijkstra on the network of routers, with link costs set by bandwidth. Game AI uses it to find paths on a map with terrain costs. Bellman-Ford appears where negative costs are real, such as currency arbitrage detection, where a loop of trades that multiplies money by more than one is a negative cycle in disguise.

Practice

Exercise 1 (easy). Run Dijkstra by hand from vertex 0 on the undirected edges 0-1 with weight 7, 0-2 with weight 3 and 2-1 with weight 2. Give the distance to every vertex. Hint: vertex 1 costs 5 through vertex 2.

Show the answer

Vertex 0 is 0, vertex 2 is 3, and vertex 1 is 5, through the route 0, 2, 1 (3 + 2 = 5). The direct edge of 7 is more expensive, so it is not used.

Exercise 2 (easy). Why does Dijkstra need every weight to be zero or more? Give a three-vertex directed example where the vertex that is closest first is not the one with the smallest final distance.

Show the answer

The proof assumes that no route through an unfinished vertex can beat a finished one. Take the directed edges 0 to 1 with weight 1, 0 to 2 with weight 5 and 2 to 1 with weight -10. Vertex 1 is the closest at first, with distance 1, so Dijkstra finishes it too early. The route 0, 2, 1 costs 5 - 10 = -5, which is cheaper. The true distance to 1 is -5. A version that never updates a finished vertex stops at 1.

Exercise 3 (easy). In Program 1, what does dist contain for an unreachable vertex, and why is it safe to add a weight to it in Python?

Show the answer

It contains math.inf, Python's float infinity. Python integers do not overflow, and math.inf plus any finite number is still math.inf, so the value does not wrap around or turn into a small number.

Exercise 4 (medium). Modify Program 1 so it prints unreachable for any vertex with distance math.inf. Test it on a graph with 5 vertices where vertex 4 has no edges.

Show the answer

After the call to dijkstra, loop over the vertices and print each one. For vertex 4 the output line is 4: unreachable, and the other vertices print their distances. With the four-vertex example, the output is 0: 0, 1: 3, 2: 1, 3: 4, and 4: unreachable, since the fifth vertex has no edges.

Exercise 5 (medium). Take the four-vertex graph of Program 1. Write the heap contents, from smallest to largest, right after vertex 2 is popped and its edges are relaxed. Hint: check the first pop in the worked example.

Show the answer

The heap holds (3, 1), (4, 1) and (6, 3). The entry (4, 1) is stale, because vertex 1 was improved to 3, and it stays in the heap until it is popped.

Exercise 6 (medium). Run Bellman-Ford by hand on the directed edges 0 to 1 with weight 2, 1 to 2 with weight -1 and 0 to 2 with weight 4. Give the distances after each pass.

Show the answer

Start: [0, inf, inf]. Pass 1 in list order: 0 to 1 gives vertex 1 the value 2. 1 to 2 gives vertex 2 the value 2 - 1 = 1. 0 to 2 gives 4, which is not less than 1, so no change. After pass 1: [0, 2, 1]. Pass 2 finds no improvement. Final: [0, 2, 1].

Exercise 7 (medium). Why does Bellman-Ford use V - 1 passes and not V? Give the reason, and say what the extra check then tells you.

Show the answer

A shortest path with no negative cycle never repeats a vertex, so it has at most V - 1 edges. After pass k, every shortest path with up to k edges is correct, so V - 1 passes finish all of them. An extra pass that still improves a distance means some walk can be made cheaper forever, so a negative cycle is reachable. V passes would also work, but the extra pass is the cycle check.

Exercise 8 (medium). Change Program 3 so it counts the heap pops that are not stale and prints the count. Then add an early exit that stops the loop when the bottom-right cell is popped. Explain why the two counts differ.

Show the answer

Add pops = 0 before the loop, put pops += 1 after the stale check, and print pops after the loop. Each cell gets exactly one non-stale pop, so the 3 by 4 grid has 12. Without the early exit, the count is 12. With if r == rows - 1 and c == cols - 1: break placed right after pops += 1, the count is 10. Both versions still print cheapest: 11, because the goal's distance is final when it is popped.

Exercise 9 (hard). Explain precisely why a negative edge can make Dijkstra give a wrong answer. Use the phrase "finished vertex" in your explanation.

Show the answer

Dijkstra finishes a vertex when it is popped with the smallest distance, and it does not expect to improve that vertex again. Its correctness depends on the claim that no later route can reach it more cheaply. A negative edge from a later vertex breaks that claim: a route through an unfinished vertex can reach the finished vertex more cheaply after all. A version that marks the vertex as done and skips it never rechecks it, so it keeps the wrong distance.

Exercise 10 (hard). A bus network has 20,000 stops and 200,000 routes with fares. Some fares are discounts that are negative. Describe which algorithm you would use, its time for these sizes, and how you would report a negative cycle to a user.

Show the answer

Bellman-Ford, because negative fares are possible. For 20,000 stops and 200,000 routes, that is about 19,999 passes times 200,000 edges, roughly four billion edge checks. That is far too many for a plain Python loop to finish in a reasonable time, so the work needs a faster language, a lower-level library, or a smaller graph. Stop early when a whole pass makes no change, which often ends the work sooner. For the report, run the extra pass after V - 1 passes. If it still improves a distance, return an error such as negative cycle: fares can be looped to lower the cost forever, and name a stop on the cycle by walking a parent array back from the improved vertex, which you record in each relaxation as Program 2 does.

What you now know

• The shortest path with weights is the path with the smallest total weight, which BFS cannot find.
• Dijkstra's algorithm finishes the closest unfinished vertex each time, using a min-heap from heapq, and relaxes each edge out of it.
• Dijkstra needs every weight to be zero or more, because a finished vertex is never improved.
• Stale heap entries are skipped with a distance check, and the parent array recovers the route.
• Bellman-Ford relaxes every edge V - 1 times, handles negative weights, and detects a reachable negative cycle with one more pass.
• Dijkstra runs in O((V + E) log V), and Bellman-Ford in O(V * E).