Graph Traversal in Python: Dijkstra’s Search
Previously we have gone through the most fundamental graph search algorithm: the Breadth First Search (BFS) and the Depth First Search (DFS). The two basic algorithms share one common point that their edges have no weights. What are weights? Simply speaking they are the “road length” or “distance between two cities”.
Weights of graph exactly reflect the real world spatial domain, though they can represent more abstract situation if necessary. But for now, a “map model” is sufficient enough for us to understand a graph and graph traversal. A graph without and with weights can be seen as illustration below: we used our previous example again for easy comparing the similarity and differences. The numbers on the line (or called edge) are arbitary assigned “distance” between nodes.
BFS and DFS have no weights considered which can’t be true in the reality since every road has their individual length. When we are making decision on which road to pick we need to consider their length. Dijkstra’s search is one of the algorithms to involve edge weights while making the node traversal.
Intutively, it is a good time to pick a starting and ending point to let the algorithm calculate. Ideally we can get back the total distance, path node, or numbers of paths. But no! There will be no destination! Dijkstra’s algorithm blindly goes to everywhere and get back all the shortest paths to every points.
What?! What’s the point? Every point?Indeed you get what you want, among all the paths one of which is what you want. But it just won’t goes directly to the point you want (to save some computation cost or so).
It doesn’t matter now, let’s just impliment it and try to understand it later.
The same graph example is used here. Only that we need to store the distance between nodes: the data is stored as the form of “dictionary of dictionary” so that we can retrive node of node and weight between node.
graph={
'A':{'B':2,'C':3},
'B':{'D':3,'E':1},
'C':{'F':2},
'D':{},
'E':{'F':1},
'F':{}
}
graph['A']# return {'B':2,'C':3}, which are the subnode of A
graph['A']['B']# return 2, which is the distance of A and BNow let’s code the algorithm. In one-short is as follow but we will explain how it grows up to this step by step.
import heapq
def dijkstra(graph,node): distances={node:float('inf') for node in graph}
distances[node]=0
came_from={node:None for node in graph} queue=[(0,node)]
while queue:
current_distance,current_node=heapq.heappop(queue)
# relaxation
for next_node,weight in graph[current_node].items():
distance_temp=current_distance+weight
if distance_temp<distances[next_node]:
distances[next_node]=distance_temp
came_from[next_node]=current_node
heapq.heappush(queue,(distance_temp,next_node))
return distances,came_fromdijkstra(graph,'A')
# return {'A': 0, 'B': 2, 'C': 3, 'D': 5, 'E': 3, 'F': 4},
# {'A': None, 'B': 'A', 'C': 'A', 'D': 'B', 'E': 'B', 'F': 'E'}# the result means for example, 'A' to 'A' is 0, 'A' to 'B' is 2
# the shortest path: for example, 'A' to 'F', we start from 'F'
# and trace back. 'F' comes from 'E', 'E' from 'B', 'B' from 'A'
Try out other example like this:
graph={
'U':{'V':2,'W':5,'X':1},
'V':{'U':2,'X':2,'W':3},
'W':{'V':3,'U':5,'X':3,'Y':1,'Z':5},
'X':{'U':1,'V':2,'W':3,'Y':1},
'Y':{'X':1,'W':1,'Z':1},
'Z':{'W':5,'Y':1}
}
dijkstra(graph,'X')#returns:
#{'U': 1, 'V': 2, 'W': 2, 'X': 0, 'Y': 1, 'Z': 2},
# {'U': 'X', 'V': 'X', 'W': 'Y', 'X': None, 'Y': 'X', 'Z': 'Y'}
You may jump out the remaining portion if you don’t have to see the algorithm explaination.
Let’s recall the previous algorith and see what makes the core lines of the algorithm:
# for BFS, the "queue" structure ensured the breadth first scanning
queue.append(node)
s=queue.pop(0)# for DFS, the "stack" plays the trick of depth first scanning
queue.append(node)
s=queue.pop()
For Dijkstra’s search, a temporary container is built in a similar way but neigher left nor right element is pop out. The minimum is pop out. We achieved the minimum distance selecton with heapq library. The following lines built the core code of Dijkstra’s search, with which the search algorithm is fake-funcational but we still need other auxiliary lines to make it work.
import heapq
queue.append(node)
distance,node=heapq.heappop(queue)We do the same thing as BFS and DFS:
import heapq
def dijkstra(graph,node): queue=[(0,node)]
while queue:
current_distance,current_node=heapq.heappop(queue)
for next_node,weight in graph[current_node].items():
#do somthing here!
return #something!
What we cared about is the distance/path from starting node to that node. So we need two containers to store these infomation. We built the containers before loop and use the while loop to fill them with correct information.
import heapq
def dijkstra(graph,node): distances={node:float('inf') for node in graph}
distances[node]=0
came_from={node:None for node in graph} queue=[(0,node)]
while queue:
current_distance,current_node=heapq.heappop(queue)
# relaxation
for next_node,weight in graph[current_node].items():
distance_temp=current_distance+weight
if distance_temp<distances[next_node]:
distances[next_node]=distance_temp
came_from[next_node]=current_node
heapq.heappush(queue,(distance_temp,next_node))
return distances,came_fromdijkstra(graph,'A')
# return {'A': 0, 'B': 2, 'C': 3, 'D': 5, 'E': 3, 'F': 4},
# {'A': None, 'B': 'A', 'C': 'A', 'D': 'B', 'E': 'B', 'F': 'E'}# the result means for example, 'A' to 'A' is 0, 'A' to 'B' is 2
# the shortest path: for example, 'A' to 'F', we start from 'F'
# and trace back. 'F' comes from 'E', 'E' from 'B', 'B' from 'A'
Wait a second, there suddenly comes out a term “relaxation” and what is that? It simply means: pick the smallest, record the smallest only. But how do we store the first value? Is there any value smaller than blank? We can’t create blank container but a container filled with infinite large number. By doing so we can anyhow store the first value and replace it with smaller value if any.
More illustration on one of the examples: If you prefer illustration, go through the following figure should be helpful for you understanding.
Start from any node, evolve from that node and expand to all it’s subnode. Update the accumulate distance if it’s smaller (this is called relaxation).
The key point here is the .heappop() method compared and pop out the smallest distance out. Dijkstra is similar to BFS but the only difference is that smaller value jumped the queue!
heapq.heappop(queue)
