Single source shortest path using BFS

#1

In the video explanation, only the shortest distance has been shown but not the shortest path. How to find the shortest path from source to destination and print that path. Please elaborate with code.

#2

hello @slow_motion
it is easy, u just have to use one parent array which will store parent of node.

for example if par[j]=c ; that means c is the parent of j .

so u can simply use this array to iterate back from destination to source.
how to update parent array?
when u r running dfs then u r passing current node and parent in ur dfs function right.
in that function simply do par[current]=parent

#3

still not clear sir…
can you please explain by taking a proper example

#4

1->2->3->4

consider this simple graph.
here ur parent array will look like
1-> -1 (-1 indicating no parent)

2-> 1 ( 1 is parent of 2)
3->2 (2 is parent of 3)
4-> 3 ( 3 is parent of 4)

now let say u started from 1 and u reached 4 and now u want to trace the path.
what u can do u can take help of this parent array.
so because right now u are on 4 u will check from where u come here using parent array , parent array has value 3 that means u came here from 3 .

again u will repeat this same process on 3 ,it will give u 2
for 2 u will get 1
parent of 1 is -1 u will stop here

#5

Thank you…finally got it

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.