BFS for single source shortest path on unweighted graph

#1

i am not able to understand the use of the parent map used in this video. also
please have a look at the distance function in my code which i wrote myself and is similar to the code in the video but my answer is coming out to be different.

#2

@alankrit.agr99
Hello Alankrit,
parent array is used to get path between source to destination

#3

and what’s wrong in my code?

#4

lets consider a simple graph

1–2--3–4--5 (bidirectional)

now
your distance array will look like (source node is 1)
node… 1 2 3 4 5
distance 0 1 2 3 4

parent array wiil look like
node… 1 2 3 4 5
parent -1 1 2 3 4

now lets say we want to print the shortest path between source (1) to destination (4)
for that we will need parent array.
first,we will see parent of 4 in our case it is 3
then,we will see parent of 3 in our case it is 2
then,we will see parent of 2 in our case it is 1
we will stop here because now we are at source node.
our path will be
4->3->2->1 (this will be your shortest path)

#5

wait i am working on it

#6

@alankrit.agr99
hello alankrit,
It was a small bug in line no - 67.
here is your corrected code- https://ide.codingblocks.com/s/174732 .
let me know if you get the error or should i tell you.

#7

@alankrit.agr99
if your doubt is resolved then please mark it resolved otherwise please ask