Chapter 7
I
Dijkstra’s algorithm
Let’s get the next-cheapest node that hasn’t already been processed.
Update the costs for its neighbors.
You already processed the poster node, but you’re updating the cost for
it. This is a big red flag. Once you process a node, it means there’s no
cheaper way to get to that node. But you just found a cheaper way to
the poster! Drums doesn’t have any neighbors, so that’s the end of the
algorithm. Here are the final costs.
It costs $35 to get to the drums. You know that there’s a path that costs
only $33, but Dijkstra’s algorithm didn’t find it. Dijkstra’s algorithm
assumed that because you were processing the poster node, there was
no faster way to get to that node. That assumption only works if you
have no negative-weight edges. So you
can’t use negative-weight edges
with Dijkstra’s algorithm.
If you want to find the shortest path in a graph
that has negative-weight edges, there’s an algorithm for that! It’s called
the
Bellman-Ford algorithm
. Bellman-Ford is out of the scope of this
book, but you can find some great explanations online.
131
Implementation
Implementation
Let’s see how to implement Dijkstra’s algorithm in code. Here’s the
graph I’ll use for the example.
To code this example, you’ll need three hash tables.
You’ll update the costs and parents hash tables as the algorithm
progresses. First, you need to implement the graph. You’ll use a hash
table like you did in chapter 6:
graph = {}
In the last chapter, you stored all the neighbors of a node in the hash
table, like this:
graph[“you”] = [“alice”, “bob”, “claire”]
But this time, you need to store the neighbors
and
the cost for getting to
that neighbor. For example, Start has two neighbors, A and B.
|
