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 + " ");
}

Complete Code: 

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

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.