Grokking Algorithms

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:

---

134