Dijkstra’s shortest path algorithm is a widely used algorithm in computer science that finds the shortest path between nodes in a graph with non-negative edge weights. It was developed by Edsger W. Dijkstra in 1956 and has since become a fundamental algorithm in network routing protocols, map applications, and many other areas of computer science. In this article, we will discuss the working of the algorithm, its implementation, and some interesting facts behind it.
Content:
How does Dijkstra’s Algorithm Work?
Dijkstra’s algorithm works by maintaining a set of unexplored nodes and a tentative distance for each node. Initially, all nodes have a tentative distance of infinity, except for the starting node which has a tentative distance of zero. The algorithm then selects the node with the smallest tentative distance and explores all its neighbors. For each neighbor, the algorithm updates its tentative distance if the new distance is smaller than the current tentative distance. This process continues until the destination node is explored or all nodes have been explored.
Dijkstras Algorithm Animation (Source: Wiki)
Step by Step explanation of Dijkstra’s Algorithm:
- Create a set of visited nodes.
- Assign a tentative distance of infinity to all nodes.
- Set the start node distance to zero [0].
- Set the starting node as the current node.
- Traverse all its neighbors and update their tentative distances if necessary.
- Mark the node as visited and move to the next non-visited node.
- Select the node with the smallest tentative distance and set it as the new current node. If all nodes have been visited, stop.
- Repeat steps 4 to 6 until the destination node is visited.
- The algorithm can be optimized by using a priority queue [minHeap] to select the node with the smallest tentative distance instead of scanning all unexplored nodes.
Implementation of Dijkstra’s Algorithm
The algorithm can be implemented using a variety of data structures, but the most common implementation uses a priority queue to keep track of unexplored nodes sorted by their tentative distances. The algorithm can also be implemented using an array.
Here is an implementation of Dijkstra’s algorithm using Python in both data structures – minHeap and Array.
Dijkstra’s Algorithm implementation using minHeap
This is the most efficient implementation of Dijkstra’s algorithm using the minHeap data structure.
Info:
The time complexity of this implementation is O((V+E)*log V)
where:
V – is the number of Vertexes (total number of cities) and E – is the total number of connections [or edges].
Vertex: Vertex is a point where two or more edges or lines meet in a graph.
Edge: Edges are connecting lines in a graph.
def dijkstraUsingHeap(connections, start):
"""
Dijkstra's algorithm using minHeap Data Strcuture
Parameters:
---------------
connections : nested dictionary with all possible connections and distances [weight]
start : starting city name [starting node]
returns:
---------------
returns a dictionary with the shortest distances to reach each place from starting city
"""
connections = self.connections
start = self.start
# first all distances to infinity in the disctionary
distances = {connection: float("inf") for connection in connections}
# distance from start to start point = 0
distances[start] = 0
minHeap = [(0, start)]
# loop through until heap is empty
# heap will be empty when all the cities are traversed
# once which are reachable from starting city.
while minHeap:
current_distance, current_city = heapq.heappop(minHeap)
# if min distance is already found - do nothing - continue
if current_distance > (distances[current_city]):
continue
# else get the distances and find the minimum one
for childCity, distance in connections[current_city].items():
NewDistance = current_distance + distance
if NewDistance < distances[childCity]:
distances[childCity] = NewDistance
heapq.heappush(minHeap, (NewDistance, childCity))
return distances
Dijkstra's Algorithm implementation using Array
This is the least efficient implementation of Dijkstra's algorithm as compared to the above implementation using minHeap.
def dijkstraUsingArray(connections, start):
"""
Dijkstra's algorithm using array Data Strcuture
Parameters:
---------------
connections : nested dictionary with all possible connections and distances [weight]
start : starting city name [starting node]
returns:
---------------
returns a dictionary with the shortest distances to reach each place from starting city
"""
connections = self.connections
start = self.start
# first all distances to infinity in the disctionary
distances = {connection: float("inf") for connection in connections}
# distance from start to start point = 0
distances[start] = 0
visited = set()
while len(visited) != len(connections):
connection, minDistance = self.__getMinimumDistance(distances, visited)
if minDistance == float("inf"):
break
visited.add(connection)
for destination, distance in connections[connection].items():
newDistance = minDistance + distance
currentDistance = distances[destination]
if currentDistance > newDistance:
distances[destination] = newDistance
return distances
def getMinimumDistance(self, distances, visited):
minDistance = float("inf")
vertex = None
for vertexId, distance in distances.items():
if vertexId in visited:
continue
if distance <= minDistance:
minDistance = distance
vertex = vertexId
return vertex, minDistance
Example: With input and output for the above implementation
Following is the same input
connections = {
"AMS": {"BOM": 3, "DEL": 4, "GOP": 1},
"BOM": {"GOP": 5, "DEL": 1},
"DEL": {"GOP": 3},
"GOP": {"DEL": 2},
}
startCity = "AMS"
# using heap data structure
distances = dijkstraUsingHeap(connections, startCity)
print(distances)
# using array data structure
distances = dijkstraUsingArray(connections, startCity)
print(distances)
After running the above code, the following is the result:
Dijkstras Algorithm Result
An interesting information - Shared by the man himself
What’s the shortest way to travel from Rotterdam to Groningen? It is the algorithm for the shortest path, which I designed in about 20 minutes. One morning I was shopping in Amsterdam with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee. I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a 20-minute invention. It was published in 1959, three years later. The publication is still quite nice.
One of the reasons that it is so nice is that I designed it without pencil and paper. Without pencil and paper, you are almost forced to avoid all avoidable complexities. Eventually, that algorithm became, to my great amazement, one of the cornerstones of my fame.
— As quoted in the article Edsger W. Dijkstra from An interview with Edsger W. Dijkstra.
0 Comments