Grokking Algorithms

Chapter 7
 
 
I
 
 
Dijkstra’s algorithm
Step 2: 
Calculate how long it takes to get to all of node B’s neighbors
 by 
following an edge from B.
Hey, you just found a shorter path to node A! It used to take 6 minutes 
to get to node A.
But if you go through node B, there’s a path that only takes 5 minutes!
When you find a shorter path for a neighbor of B, update its cost. In this 
case, you found 
• A shorter path to A (down from 6 minutes to 5 minutes)
• A shorter path to the finish (down from infinity to 7 minutes)
Step 3: 
Repeat!
Step 1 again: 
Find the node that takes the least amount of time
to get to. You’re done with node B, so node A has the next smallest
time estimate.

---

119
Working with Dijkstra’s algorithm
Step 2 again:
 
Update the costs for node A’s neighbors.
Woo, it takes 6 minutes to get to the finish now!
You’ve run Dijkstra’s algorithm for every node (you don’t need to run it 
for the finish node). At this point, you know
• It takes 2 minutes to get to node B.
• It takes 5 minutes to get to node A.
• It takes 6 minutes to get to the finish.
I’ll save the last step, calculating the final path, for the next section. For 
now, I’ll just show you what the final path is.
Breadth-first search wouldn’t have found this as the shortest path, 
because it has three segments. And there’s a way to get from the start to 
the finish in two segments.

---

120
Chapter 7
 
 
I
 
 
Dijkstra’s algorithm
In the last chapter, you used breadth-first search to find the shortest 
path between two points. Back then, “shortest path” meant the path 
with the fewest segments. But in Dijkstra’s algorithm, you assign a 
number or weight to each segment. Then Dijkstra’s algorithm finds the 
path with the smallest total weight.
To recap, Dijkstra’s algorithm has four steps:
1. Find the cheapest node. This is the node you can get to in the least 
amount of time.
2. Check whether there’s a cheaper path to the neighbors of this node. 
If so, update their costs.
3. Repeat until you’ve done this for every node in the graph.
4. Calculate the final path. (Coming up in the next section!)