Grokking Algorithms

Chapter 7
 
 
I
 
 
Dijkstra’s algorithm
Here’s the code to make the hash table for the parents:
parents = {}
parents[“a”] = “start”
parents[“b”] = “start”
parents[“fin”] = None
Finally, you need an array to keep track of all the nodes you’ve already 
processed, because you don’t need to process a node more than once:
processed = []
That’s all the setup. Now let’s look at the algorithm.
I’ll show you the code first and then walk through it. Here’s the code:
node = find_lowest_cost_node(costs) 
while node is not None: 
cost = costs[node]
neighbors = graph[node]
for n in neighbors.keys(): 
new_cost = cost + neighbors[n] 
if costs[n] > new_cost:
costs[n] = new_cost
parents[n] = node
processed.append(node)
node = find_lowest_cost_node(costs) 
That’s Dijkstra’s algorithm in Python! I’ll show you the code for the 
function later. First, let’s see this 
find_lowest_cost_node 
algorithm 
code in action.
Find the lowest-cost node
 that you haven’t processed yet.
 If you’ve processed all the nodes, this while loop is done.
Go through all the neighbors of this node.
 
If it’s cheaper to get to this neighbor
by going through this node …
 … update the cost for this node.
 This node becomes the new parent for this neighbor.
 Mark the node as processed.
 Find the next node to process, and loop.

---

135
Implementation
Find the node with the lowest cost.
Get the cost and neighbors of that node.
Loop through the neighbors.
Each node has a cost. The cost is how long it takes to get to that node 
from the start. Here, you’re calculating how long it would take to get to 
node A if you went Start > node B > node A, instead of Start > node A.
Let’s compare those costs.

---

136