# 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 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
```

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