Problem Statement: Given an unweighted graph, a source and a destination, we need to find shortest path from source to destination in the graph in most optimal way.

Output : Optimally the shortest path between 0 and 7 is 0->3->7 with path length of 3.

Explanation: The idea here is to use Breadth First Technique or BFS.In continuation to our previous post on Graphs where we implemented BFS by using queue data structure and a boolean visited array, here we also maintain a distance array for all nodes in our graph.Here’s the algorithm,

1. Initialize dist[V]={INT_MAX , INT_MAX , INT_MAX………,INT_MAX };
2. dist[source] = 0;
3. Create a queue q;
4. Initialize bool visited={false, false , false, ……….,false};
5. q.push(source); visited[source]=true;
6. Loop of BFS with some tweaks.

while( !q.empty() )
{
     int node = q.pop();
     for(int x : adj[node])
     {
          if(visited[x] == false)
          {
               distance[x] = distance[node] + 1;
               visited[x] = true;
               q.push(x);
          }
     }
}

This article has been contributed by Prashant Singh Thakur.