Dijkstra’s algorithm is a well-known algorithm in computer science that is used to find the shortest path between two points in a weighted graph. The algorithm uses a priority queue to explore the graph, assigning each vertex a tentative distance from a source vertex and then iteratively updating this value as it visits neighboring vertices.
What Is Dijkstra’s Algorithm?
Dijkstra’s algorithm is used to find the shortest path between two points in a weighted graph. It is essential for solving problems such as network routing and mapping.
We will go over how Dijkstra’s algorithm works, provide an example on a small graph, demonstrate its implementation in Python and touch on some of its practical applications.
How Dijkstra’s Algorithm Works
Dijkstra’s algorithm works on directed graphs, where nodes are connected with weighted non-negative edges. The algorithm finds the distance from a single source node to all other nodes in the graph. If we only care about the shortest distance to a single target node, we can simply stop the algorithm after that particular path has been found.
To initialize our graph, we first assign values to every node, which represents the node’s distance from the source. The source node receives a value of 0, the rest receive an initial (tentative) value of infinity ∞.
We will use this example graph where the source node is s, and there are four target nodes: a, b, c, and d.
In the next step, we take the smallest-value unprocessed node (shaded gray). We then assign its value as the minimum of the current value, or any of the neighboring values plus the edge distance connecting them. In this first step, we assign s to min(0, ∞+4, ∞+8). So we keep the value as 0, then mark the node as completed (shaded with black).
Next, we take all our neighboring nodes and assign them again to the minimum of their current value, or their neighboring values plus the corresponding edge distances.
We take the smallest-valued node (b in this case) and treat it as our new node of interest.
We then repeat the process with the next node: update its neighbors’ values, mark it as completed and find the next minimum-valued node.
Note that once a node is marked as completed, its value is definitively the shortest path from the target. If this is the only node we care about, we can stop here. Or we can continue to find the shortest paths to all other nodes by repeating the process:
In summary, the steps are:
- Initialize the source node to take value 0 and all other nodes to ∞. Start with node 0 as the “current node.”
- Find all neighboring nodes and update their values to either the minimum of their value or the value of the current node plus its distance. Mark the node as finished.
- Assign the minimum-valued unfinished node as the current node.
- Repeat steps 2 and 3 until all nodes (or a specific node of interest) are finished.
Implementing Dijkstra’s Algorithm in Python
Implementing Dijkstra’s algorithm in Python is a good exercise for understanding how it works. We will cover the important components of a Python implementation.
First, we can represent a directed graph using a dictionary adjacency list:
graph={
's':{'a':8,'b':4},
'a':{'b':4},
'b':{'a':3,'c':2,'d':5},
'c':{'d':2},
'd':{}
}Next we make a simple class for a node.
class Node:
def __init__(self,x_coord,y_coord):
self.d=float('inf') #current distance from source node
self.parent=None
self.finished=FalseWe use the variable d to store the distance and parent to store the parent node (used for re-tracing the shortest path). We will keep the unfinished nodes in a queue, ordered by their distance to the source node. The code for running Dijkstra’s algorithm might look something like this:
def dijkstra(graph,source):
nodes={}
for node in graph:
nodes[node]=Node()
nodes[source].d=0
queue=[(0,source)] #priority queue
while queue:
d,node=heapq.heappop(queue)
if nodes[node].finished:
continue
nodes[node].finished=True
for neighbor in graph[node]:
if nodes[neighbor].finished:
continue
new_d=d+graph[node][neighbor]
if new_d<nodes[neighbor].d:
nodes[neighbor].d=new_d
nodes[neighbor].parent=node
heapq.heappush(queue,(new_d,neighbor))
return nodesThere are a couple of important notes for this implementation. First, we keep the unfinished nodes in queue, using the built-in Python library heapq to push and pop nodes based on their distance value. Additionally, the returned value is a dictionary of nodes, where we can use the node’s parent, e.g. nodes['c'].parent to traverse the shortest path back to the source node.
Applications for Dijkstra’s Algorithm
Dijkstra’s algorithm can be used to find the shortest route between two points on a map, taking into account traffic conditions and other obstacles. In network routing, it can be used to find the shortest path between two computers on a network, while in computer networks, it can be used to find the fastest route between two nodes in a distributed system.
It is also used in GIS applications to find the shortest paths between geographic points. Generally, Dijkstra’s algorithm is a tool that has many real-world applications in various fields, particularly those that require efficient pathfinding in graph structures.
