This is the continuation of Part 3a. Here we will finally implement Dijkstra’s algorithm in Python.

Part 1 – Introduction to Dijkstra’s shortest path algorithm
Part 2a – Graph implementation in Python
Part 2b – Graph implementation in Java
Part 3a – Priority queue in Python
Part 3b – Priority queue in Java
Part 4a – Python implementation
Part 4b – Java implementation

In part 1 we described the algorithm as follows:

——————-

Step 0 (initialization): Assign to all nodes a distance value of ‘inf’, except for the source node which has a distance of zero. Initialize an empty set S. Initialize a predecessor dictionary.

Repeat loop:
____Step 1: add to S the node with the smallest distance (among the nodes that touch S via an edge). Call that node u.
____Step 2: for u consider all new outgoing edges {u, v1}, {u, v2}, …, {u, vk} (i.e. edges that lead to nodes which are not yet in S). Check if these edges lead to a smaller distance value for the nodes v1, v2, …, vk. If it does for vj, update the distance for vj to the smaller value and set the predecessor of vj to u.
____ If there are no nodes left that touch S via an edge, then break the loop.

——————-

Here is the implementation in Python:

# Dijktra's shortest path algorithm. Prints the path from source to target.


def dijkstra(adj, source, target):
    INF = ((1<<63) - 1)//2
    pred = { x:x for x in adj }
    dist = { x:INF for x in adj }
    dist[source] = 0
    PQ = []
    heapq.heappush(PQ, [dist[source], source])

    while(PQ):
        u = heapq.heappop(PQ)  # u is a tuple [u_dist, u_id]
        u_dist = u[0]
        u_id = u[1]
        if u_dist == dist[u_id]:
            #if u_id == target:
            #    break
            for v in adj[u_id]:
               v_id = v[0]
               w_uv = v[1]
               if dist[u_id] +  w_uv < dist[v_id]:
                   dist[v_id] = dist[u_id] + w_uv
                   heapq.heappush(PQ, [dist[v_id], v_id])
                   pred[v_id] = u_id
               
    if dist[target]==INF:
        stdout.write("There is no path between " + source + " and " + target)
    else:
        st = []
        node = target
        while(True):
            st.append(str(node))
            if(node==pred[node]):
                break
            node = pred[node]
        path = st[::-1]
        stdout.write("The shortest path is: " + " ".join(path))

– Lines 5 to 9 show the initialization. INF is initialized to half of the maximum value of a signed 64 bit integer (a signed 64 bit integer can display integers from to .
– In lines 9 and 10 we initialize a priority queue and insert the tuple (dist[source], source) since we start with the source node.
– Lines 12 to 25 implement the repeating loop. In line 13 we try to find the next node with the smallest distance value. We do this with a priority queue. In line 16 we discard “wrong tuples”, see also Part 3a.
– Lines 17 and 18 are optional. They make the algorithm stop once the minimum distance for the target node has been found. Note though that if you uncomment these lines the distances to other nodes beside the target node are not necessarily found, so uncomment these lines only if you are interested in a particular target node.
– In line 27 we check whether a path has been found.
– In lines 30 to 38 we reconstruct the shortest path with the help of the predecessor dictionary.
In particular this is done in lines 32 to 36 where we follow the shortest path backwards from the target to the source. We recognize the source by checking if pred[node] == node, see also the way we initialized the predecessor dictionary in line 6.

Notes:
– Dijkstra’s algorithm only works if the edge weights are positive.
– We’ve used a priority queue that does not support a decrease-key operation as described in Part 3a. This differs from the description in the literature where a priority queue with a decrease-key operation is used.
– You have probably noticed that in our implementation we did not use a set S that contains the nodes for which we have found the minimum distance. The priority queue holds those nodes that “touch” our set S via an edge, see also part 1. When a node gets extracted from the priority queue it means we are adding it to our set S.
– Line 22 automatically ignores edges that go to nodes v within S because dist[u_id] + w_uv < dist[v_id] can never be true due to the fact that dist[v_id] is the minimum distance for v once it has been added to S.

References:
1. Wikipedia article on Dijkstra’s algorithm
2. Stackoverflow discussion on the priority queue used in Dijkstra’s algorithm.
Here is another discussion on the same topic.
And here is another one.
3. Priority Queues and Dijkstra’s Algorithm is a paper that examines how fast Dijkstra’s algorithm is with different priority queue implementations, in particular the priority queue without a decrease-key operation.
4. Stackoverflow discussion on how to implement a priority queue that supports the operation decrease-key.

Exercises:
1) In Part 2a we implemented a graph. Find the minimum distance and shortest path from node ‘a’ to node ‘i’ for that graph. Compare your findings with Part 1.

2) Print the predecessor dictionary and the distance dictionary. Compare the distance dictionary with the distances we have found in Part 1.

Solution:
Python code

import heapq
from sys import stdin, stdout

# Dijktra's shortest path algorithm. Prints the path from source to target.


def dijkstra(adj, source, target):
    INF = ((1<<63) - 1)//2
    pred = { x:x for x in adj }
    dist = { x:INF for x in adj }
    dist[ source ] = 0
    PQ = []
    heapq.heappush(PQ, [dist[ source ], source])

    while(PQ):
        u = heapq.heappop(PQ)  # u is a tuple [u_dist, u_id]
        u_dist = u[0]
        u_id = u[1]
        if u_dist == dist[u_id]:
            #if u_id == target:
            #    break
            for v in adj[u_id]:
               v_id = v[0]
               w_uv = v[1]
               if dist[u_id] +  w_uv < dist[v_id]:
                   dist[v_id] = dist[u_id] + w_uv
                   heapq.heappush(PQ, [dist[v_id], v_id])
                   pred[v_id] = u_id
               
    if dist[target]==INF:
        stdout.write("There is no path between ", source, "and", target)
    else:
        st = []
        node = target
        while(True):
            st.append(str(node))
            if(node==pred[node]):
                break
            node = pred[node]
        path = st[::-1]
        stdout.write("The shortest path is: " + " ".join(path) + "\n\n")
        stdout.write("The distance from 'a' to 'i' is: " + str(dist['i']) + "\n\n")
        stdout.write("distance dictionary: " + str(dist) + "\n\n")
        stdout.write("predecessor dictionary: " + str(pred))
    
#----------------------------------------------------------

def main():
    
    adj = {'c': [('b', 0.32), ('e', 0.17), ('f', 0.91)],
         'g': [('d', 0.17), ('e', 0.27), ('h', 0.92)],
         'i': [('e', 1.98), ('f', 0.13), ('h', 0.22)],
         'f': [('c', 0.91), ('e', 0.33), ('i', 0.13)],
         'h': [('e', 0.18), ('g', 0.92), ('i', 0.22)],
         'd': [('a', 0.72), ('e', 0.29), ('g', 0.17)],
         'a': [('b', 0.95), ('d', 0.72), ('e', 1.75)],
         'e': [('a', 1.75), ('b', 0.82), ('c', 0.17), ('d', 0.29), ('f', 0.33), ('g', 0.27), ('h', 0.18), ('i', 1.98)],
         'b': [('a', 0.95), ('c', 0.32), ('e', 0.82)]}
        
    dijkstra(adj, 'a', 'i')

#----------------------------------------------------------

if __name__ == "__main__":
    main()

The output is:

The shortest path is: a d e h i

The distance from 'a' to 'i' is: 1.41

distance dictionary: {'a': 0, 'c': 1.18, 'b': 0.95, 'e': 1.01, 'd': 0.72, 'g': 0.89, 'f': 1.34, 'i': 1.41, 'h': 1.19}

predecessor dictionary: {'a': 'a', 'c': 'e', 'b': 'a', 'e': 'd', 'd': 'a', 'g': 'd', 'f': 'e', 'i': 'h', 'h': 'e'}

The output coincides with shortest path and distances that we have found in part 1.