Suppose you’re choosing a route to work. One route has fewer turns, but another takes less time. Counting segments alone won’t tell you which is faster. Give each edge—the connection between two points—a number for its travel time. That number is its weight. section 9.1
A graph whose edges have weights is a weighted graph. To compare routes, add the weights along each path. Breadth-first search finds a path with the fewest segments in an unweighted graph; Dijkstra’s algorithm looks for the path with the smallest total weight. section 9.1 section 9.2
A longer route that takes less time
From Start, going straight to A takes 6 minutes. Going through B takes 2 minutes to reach B and another 3 to reach A: 5 minutes total. Continuing from A to Finish adds 1 minute, making the route through B take 6 minutes. The shorter-looking route through A takes 7 minutes. section 9.1 section 9.5
Weights can represent money instead of time. In a chain of trades toward a piano, each edge’s weight is the money needed for that trade. The best path is the one with the lowest total cost—not necessarily the fewest trades. section 9.3
Keep edge weight separate from node cost: the weight belongs to one connection, while a node’s cost is the total needed to reach it from the start. Dijkstra’s algorithm updates that cost when it finds a cheaper route through a neighboring node. Negative edge weights call for a different algorithm, Bellman–Ford. section 9.5 section 9.2
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 adds a neighbor’s edge weight to the current node’s cost, then updates the neighbor’s cost and parent if the new route is cheaper. section 9.5
