Example code from the DSA For Non-Traditionals: 7 - Dijkstra's algorithm in the Travis Media Community - https://community.travis.media/recordings/dsa-for-non-traditionals-dijkstras-algorithm

dijkstras-algorithm.py

# First, let's implement the graph. This time we'll need to store the neighbors AND the cost for getting to that neighbor.

# Start has two neighbors A and B
graph = {}
graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2

# Graph["start"] is a hash table
# Get all the neighbors for start like this

print(graph["start"].keys())
# ["a", "b"]

# So there is 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"] = {}

# Thats the full GRAPH

# 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 which in Python is

infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity

# Next we need another 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 = []

# Now let's take a look at a diagram of the algorithm.


def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:  # Go through each node.
        cost = costs[node]
        # If it’s the lowest cost so far and hasn’t been processed yet …
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost  # … set it as the new lowest-cost node.
            lowest_cost_node = node
    return lowest_cost_node


# Find the lowest-cost node that you haven't processed yet
node = find_lowest_cost_node(costs)
while node is not None:  # If you've processed all the nodes, this while loop is done.
    cost = costs[node]
    neighbors = graph[node]
    for n in neighbors.keys():  # Go through all the neighbors of this node
        new_cost = cost + neighbors[n]
        # If it's cheaper to get to this neighbor by going through this node...
        if costs[n] > new_cost:
            costs[n] = new_cost  # ...update the cost for this node
            # This node becomes the new parent for this neighbor
            parents[n] = node
    processed.append(node)  # Mark the node as processed
    # Find the next node to process, and loop
    node = find_lowest_cost_node(costs)