Print all paths from a given source to a destination using BFS

Given a directed graph, a source vertex ‘src’ and a destination vertex ‘dst’, print all paths from given ‘src’ to ‘dst’.

Consider the following directed graph. Let the src be 2 and dst be 3. There are 3 different paths from 2 to 3.

We have already discussed Print all paths from a given source to a destination using DFS.

Below is BFS based solution.

Algorithm :

create a queue which will store path(s) of type vector
initialise the queue with first path starting from src

Now run a loop till queue is not empty
   get the frontmost path from queue
   check if the lastnode of this path is destination
       if true then print the path
   run a loop for all the vertices connected to the
   current vertex i.e. lastnode extracted from path
      if the vertex is not visited in current path
         a) create a new path from earlier path and 
             append this vertex
         b) insert this new path to queue
// CPP program to print all paths of source to
// destination in given graph
#include <bits/stdc++.h>
using namespace std;
// utility function for printing
// the found path in graph
void printpath(vector<int>& path)
    int size = path.size();
    for (int i = 0; i < size; i++) 
        cout << path[i] << " ";    
    cout << endl;
// utility function to check if current
// vertex is already present in path
int isNotVisited(int x, vector<int>& path)
    int size = path.size();
    for (int i = 0; i < size; i++) 
        if (path[i] == x) 
            return 0; 
    return 1;
// utility function for finding paths in graph
// from source to destination
void findpaths(vector<vector<int> >&g, int src, 
                                 int dst, int v)
    // create a queue which stores
    // the paths
    queue<vector<int> > q;
    // path vector to store the current path
    vector<int> path;
    while (!q.empty()) {
        path = q.front();
        int last = path[path.size() - 1];
        // if last vertex is the desired destination
        // then print the path
        if (last == dst) 
        // traverse to all the nodes connected to 
        // current vertex and push new path to queue
        for (int i = 0; i < g[last].size(); i++) {
            if (isNotVisited(g[last][i], path)) {
                vector<int> newpath(path);
// driver program
int main()
    vector<vector<int> > g;
    // number of vertices
    int v = 4;
    // construct a graph
    int src = 2, dst = 3;
    cout << "path from src " << src
         << " to dst " << dst << " are ";
    // function for finding the paths
    findpaths(g, src, dst, v);
    return 0;


path from src 2 to dst 3 are 
2 0 3 
2 1 3 
2 0 1 3

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

This article is attributed to GeeksforGeeks.org

leave a comment



load comments

Subscribe to Our Newsletter