Shortest Path in an unweighted Graph

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.

unweighted graph

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);
          }
     }
}
For complete code refer to this video.

This article has been contributed by Prashant Singh Thakur.

Write a comment