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)
```