The route with the fewest stops isn’t always the fastest. If each road has a travel time, you want the path with the lowest total time—not necessarily the fewest edges. Dijkstra’s algorithm finds that path in a weighted graph whose edge weights are nonnegative. For an unweighted graph, breadth-first search finds the path with the fewest edges instead. section 9.0 section 9.6
A six-minute route
Suppose Start → A takes 6 minutes, Start → B takes 2, B → A takes 3, B → Finish takes 5, and A → Finish takes 1. Going straight through A takes 7 minutes. Going through B and then A takes 2 + 3 + 1 = 6 minutes, even though it uses an extra edge. section 9.1 section 9.5
To find that route, keep a tentative cost for each node—the cheapest known cost from Start—and a parent for tracing the route back.
- Give Start’s neighbors their edge costs. Give nodes you cannot reach yet a cost of infinity. section 9.1 section 9.5
- Choose the lowest-cost node you haven’t processed. Here, that is B at 2 minutes. section 9.1
- Check each of its out-neighbors. Going through B lowers A’s cost from 6 to 5 and gives Finish a cost of 7. Update a neighbor’s parent whenever you find a cheaper route to it. section 9.1 section 9.5
- Mark B processed and repeat. Processing A lowers Finish’s cost from 7 to 6. Follow the recorded parents backward from Finish to recover Start → B → A → Finish. section 9.1 section 9.3 section 9.5
Why can you leave a processed node alone? With nonnegative weights, reaching the current cheapest node through another, more expensive node cannot make its cost smaller. A negative edge breaks that reasoning: a later route might make an already processed node cheaper. Use Bellman–Ford instead when edges can have negative weights. section 9.3 section 9.4 section 9.6
node = find_lowest_cost_node(costs) #1
while node is not None: #2
cost = costs[node]
neighbors = graph[node]
for n in neighbors.keys(): #3
new_cost = cost + neighbors[n]
if costs[n] > new_cost: #4
costs[n] = new_cost #5
parents[n] = node #6
processed.add(node) #7
node = find_lowest_cost_node(costs) #8
#1 Finds the lowest-cost node that you haven’t processed yet
#2 If you’ve processed all the nodes, this while loop is done.
#3 Goes through all the out-neighbors of this node
#4 If it’s cheaper to get to this out-neighbor by going through this node . . .
#5 . . . updates the cost for the neighbor
#6 This node becomes the new parent for this out-neighbor.
#7 Marks the node as processed
#8 Finds the next node to process and loops
The Python loop selects an unprocessed lowest-cost node, checks its neighbors, updates cheaper costs and parents, then marks the node processed. section 9.5
The weights need not represent minutes. In a trading graph, an edge can represent money paid for a trade; the same steps find a least-cost sequence of trades. section 9.3
