Suppose you can trade your way from a book to a piano, but some trades require payment. Each trade has an edge cost: the price of making that one trade. A node’s cost is different: it is the total amount needed to reach that item by the cheapest route found so far. section 9.3
Dijkstra’s algorithm keeps a costs table and repeatedly chooses the cheapest unprocessed node. For each of its out-neighbors, add the edge cost to the current node’s cost. If that route is cheaper than the neighbor’s recorded cost, update the table and record the current node as its parent. The parents let you reconstruct the route, not just its total cost. section 9.3 section 9.5
Minutes from Start to Finish
Start → A takes 6 minutes; Start → B takes 2. Begin with costs of 6 for A, 2 for B, and infinity for Finish because no route to it is known yet. From B, reaching A takes 2 + 3 = 5 minutes, so replace A’s cost of 6 with 5. B → Finish costs 2 + 5 = 7 minutes. Once A has the lower cost of 5, going from A to Finish takes 5 + 1 = 6 minutes, improving Finish’s cost from 7 to 6. section 9.5
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 shows the central calculation, `new_cost = cost + neighbors[n]`, followed by the comparison that decides whether to update a neighbor’s cost and parent. section 9.5
