|
This post is completed by 1 user
|
Add to List |
441. Print All Paths in Dijkstra's Shortest Path Algorithm
Objective: Given a graph and a source vertex write an algorithm to find the shortest path from the source vertex to all the vertices and print the paths all well.
Example:
We strongly recommend reading the following before continuing to read
We will use the same approach with some extra steps to print the paths from the source vertex to all the vertices.
Use the parent [] to keep track of parent vertices. Say if parent[x] = y then for vertex ‘x' the parent vertex is ‘y' which means the shortest path to vertex ‘x' goes via vertex ‘y', i.e ‘source--->y--->x'
The parent of source vertex will be -1.
Once the algorithm is completed, the parent [] will have all the information to print the path. Use recursion to print the paths.
public void printPathUtil(int parent[], int destination){
//if vertex is source then stop recursion
if(parent[destination] == -1) {
System.out.print("0 ");
return;
}
printPathUtil(parent, parent[destination]);
System.out.print(destination + " ");
}
Output:
Dijkstra Algorithm: (With all paths) 0--> 0: distance=0 Path : 0 0--> 1: distance=4 Path : 0 2 1 0--> 2: distance=3 Path : 0 2 0--> 3: distance=6 Path : 0 2 1 3 0--> 4: distance=8 Path : 0 2 1 3 4 0--> 5: distance=14 Path : 0 2 1 3 4 5