Shortest Path Algorithms I – Dijkstra

The shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized. (Wikipedia) In this and coming posts some of the most common algorithms to solve the shortest path problems will be explained. Today’s topic is Dijkstra.

As we’ve discussed in Intro to Graph Algorithms – BFS & DFS, BFS would be able to find the shortest path in an unweighted graph. When it comes to the weighted graph, however, we need to modify it a little bit. In terms of the data structure, we would use Priority Queue, which is similar to Queue but each element has a priority associated with it.

Initially, we put the source vertex s into our priority queue pq and overestimate the distance between s and others as infinity, and, of course, the distance between the s and itself is 0. Then each time we will pop the first node from pq, and mark it as visited. For each of its neighbours adj, if it’s not visited and the distance between s and adj through this node is smaller than adj‘s original tentative estimation, we would update it to the smaller value, and push it into pq with the updated distance as its priority. We would keep doing this until pq is empty, or we can simply stop when we add the target node into the visited.

Let’s now take a look at code. Firstly we need a graph.

graph = {
    'A': {'B':5, 'C':1},
    'B': {'A':5, 'C':2, 'D':1},
    'C': {'A':1, 'B':2, 'D':4, 'E':8},
    'D': {'B':1, 'C':4, 'E':3, 'F':6},
    'E': {'C':8, 'D':3},
    'F': {'D':6}
}

Then let’s initialize pq, visited, distance. Notably, parent is to record the shortest path, and heapq is the Python package for the priority queue.

import heapq

src = 'A'

pq = [(0,src)]
visited = set()
parent = {src: None}
distance = {src: 0,
'B':float('inf'), 
'C':float('inf'), 
'D':float('inf'), 
'E':float('inf'), 
'F':float('inf'), 
}

Finally it’s the loop.

while pq:
    dist, node = heapq.heappop(pq)
    visited.add(node)
    for adj,d in graph[node].items():
        if adj not in visited:
            if dist + d < distance[adj]:
                heapq.heappush(pq,(dist+d,adj))
                parent[adj] = node
                distance[adj] = dist + d

print(distance,parent)

Reference

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments