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.
|
