Dijkstra’s Shortest Path Algorithm
The Dijkstra’s Shortest Path algorithm is a greedy algorithm which is used for finding the shortest path between nodes in a graph. This algorithm finds the shortest path between the two nodes but it can be used for finding the shortest paths from a single node to all other nodes by iterating the algorithm for more than once (Total number of nodes – 1).
Working of Dijkstra’s Shortest Path algorithm
Dijkstra’s Shortest Path algorithm is working on the greedy approach. In this shortest path tree with given source as a root is generated. And every step of the algorithm finds the vertex has a minimum distance from the source.
It uses the property in the opposite direction that if the shortest path between vertices A and C that is A -> C and B -> C is the subpath in A -> C then B -> C is also the shortest path between vertices B and C.
Example of Dijkstra’s algorithm
Greedy algorithm approach is used for finding the shortest path between nodes in a graph.
Below is the example of Dijkstra’s algorithm with input- output constraint and the solution for the example.
Input and Output of the Example
Given the weighted graph G, and the task is used to find the shortest path between nodes.
Solution:
Stepwise Solution of the Problem Example using Dijkstra’s Shortest Path Algorithm
Step 1: Start with the given weighted graph
Step 2: Pick the starting vertex and assign infinity path values to all other vertices.
Step 3: Go to each vertex adjacent to previous vertex and update its path length.
Step 4: If the path length of adjacent vertex is less than new path don’t update it and avoid updating path lengths of already visited vertices.
Step 5: After each iteration, pick unvisited with least path and repeat until all vertices have been visited.
Step 6: Return the solution
Pseudocode for Dijkstra’s Shortest Path algorithm
Here’s Pseudocode for finding the shortest path between the nodes in a graph using greedy algorithm approach.
Dijkstra(Graph, source):
// Initializations
for each vertex v in Graph:
// Unknown distance function from source to
//each node set to infinity
dist[v] <- infinity
// All nodes initially in Q
add v to Q
// Distance from source to source is set to 0
dist[source] := 0
while Q is not empty:
v <- vertex min dist[v] from Q
remove v from Q
for each neighbor u of v:
alt := dist[v] + length(v, u)
// A shorter path to u has been found
if alt < dist[u]:
// Update distance of u
dist[u] := alt
return dist[]
Implementation of Dijkstra’s Shortest Path Algorithm in Python
# Dijkstra's Algorithm in Python
import sys
# Function to find which vertex is to be visited next
def next_to_visited():
global visited
v = -10
for index in range(num_of_vertices):
if visited[index][0] == 0 and (v < 0 or visited[index][1] <= visited[v][1]):
v = index
return v
# Function to find the shortest path between nodes in a graph
def dijkstra():
for vertex in range(num_of_vertices):
# Find next vertex to be visited
visit = next_to_visited()
for index in range(num_of_vertices):
# Updating new distances
if vertices[visit][index] == 1 and visited[index][0] == 0:
new_distance = visited[visit][1] + edges[visit][index]
if visited[index][1] > new_distance:
visited[index][1] = new_distance
visited[visit][0] = 1
# Printing the distance
def print_dist():
i = 0
for distance in visited[1:]:
print("Distance from S ->", chr(ord('A')+i), ":",distance[1])
i = i + 1
# Driver Code
# Providing the graph
# 2D array to represnt the vertex structure
vertices = [[0, 1, 1, 1],
[1, 0, 1, 0],
[1, 1, 0, 1],
[1, 0, 1, 0]]
# 2D array to represnt the edge structure
edges = [[0, 1, 2, 5],
[1, 0, 2, 0],
[2, 2, 0, 4],
[5, 0, 4, 0]]
# calculate Number of vertices
num_of_vertices = len(vertices[0])
# store the visited edge and vertex
visited = [[0, 0]]
for i in range(num_of_vertices-1):
visited.append([0, sys.maxsize])
# Function calling
dijkstra()
print_dist()