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).
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.
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.
Given the weighted graph G, and the task is used to find the shortest path between nodes.
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
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
# 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 and (v < 0 or visited[index] <= visited[v]): 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: new_distance = visited[visit] + edges[visit][index] if visited[index] > new_distance: visited[index] = new_distance visited[visit] = 1 # Printing the distance def print_dist(): i = 0 for distance in visited[1:]: print("Distance from S ->", chr(ord('A')+i), ":",distance) 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) # 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()