7
Dijkstra’s
algorithm
116
Chapter 7
I
Dijkstra’s algorithm
In the last chapter, you figured out a way to get from point A to point B.
It’s not necessarily the fastest path. It’s the shortest path, because it has
the least number of segments (three segments). But suppose you add
travel times to those segments. Now you see that there’s a faster path.
You used breadth-first search in the last chapter. Breadth-first search
will find you the path with the fewest segments (the first graph shown
here). What if you want the fastest path instead (the second graph)? You
can do that
fastest
with a different algorithm called
Dijkstra’s algorithm.
Working with Dijkstra’s algorithm
Let’s see how it works with this graph.
Each segment has a travel time in minutes. You’ll use Dijkstra’s
algorithm to go from start to finish in the shortest possible time.
117
Working with Dijkstra’s algorithm
If you ran breadth-first search on this graph, you’d get this
shortest path.
But that path takes 7 minutes. Let’s see if you can find a path that takes
less time! There are four steps to Dijkstra’s algorithm:
1. Find the “cheapest” node. This is the node you can get to in the least
amount of time.
2. Update the costs of the neighbors of this node. I’ll explain what I
mean by this shortly.
3. Repeat until you’ve done this for every node in the graph.
4. Calculate the final path.
Step 1:
Find the cheapest node. You’re standing at the start, wondering
if you should go to node A or node B. How long does it take to get to
each node?
It takes 6 minutes to get to node A and 2 minutes to get to node B.
The rest of the nodes, you don’t know yet.
Because you don’t know how long it takes to get
to the finish yet, you put down infinity (you’ll see
why soon). Node B is the closest node … it’s 2
minutes away.
|
