Chapter 7
I
Dijkstra’s algorithm
How do you represent the weights of those edges? Why not just use
another hash table?
graph[“start”] = {}
graph[“start”][“a”] = 6
graph[“start”][“b”] = 2
So
graph[“start”]
is a hash table. You can get all the neighbors for
Start like this:
>>> print graph[“start”].keys()
[“a”, “b”]
There’s an edge from Start to A and an edge from Start to B. What if you
want to find the weights of those edges?
>>> print graph[“start”][“a”]
2
>>> print graph[“start”][“b”]
6
Let’s add the rest of the nodes and their neighbors to the graph:
graph[“a”] = {}
graph[“a”][“fin”] = 1
graph[“b”] = {}
graph[“b”][“a”] = 3
graph[“b”][“fin”] = 5
graph[“fin”] = {}
The finish node doesn’t have any neighbors.
133
Implementation
The full graph hash table looks like this.
Next you need a hash table to store the costs for each node.
The
cost
of a node is how long it takes to get to that
node from the start. You know it takes 2 minutes from
Start to node B. You know it takes 6 minutes to get to
node A (although you may find a path that takes less
time). You don’t know how long it takes to get to the
finish. If you don’t know the cost yet, you put down
infinity. Can you represent
infinity
in Python? Turns
out, you can:
infinity = float(“inf”)
Here’s the code to make the costs table:
infinity = float(“inf”)
costs = {}
costs[“a”] = 6
costs[“b”] = 2
costs[“fin”] = infinity
You also need another hash table for the parents:
|
