• Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.

In this post I will be discussing two ways of finding all paths between a source node and a destination node in a graph:

• Using DFS: The idea is to do Depth First Traversal of given directed graph. Start the traversal from source. Keep storing the visited vertices in an array say ‘path[]’. If we reach the destination vertex, print contents of path[]. The important thing is to mark current vertices in path[] as beingVisited, so that the traversal doesn’t go in a cycle.
```                ```
// Java Implementation
// Prints all paths from 's' to 'd'
public void printAllPaths(int s, int d)
{
boolean[] beingVisited = new boolean[v];
ArrayList currentPath = new ArrayList<>();

dfs(s, d, beingVisited, currentPath);
}

private void dfs(Integer u, Integer d, boolean[] beingVisited, List currentPath)
{
beingVisited[u] = true; // to avoid cycle

if (u.equals(d))
{
System.out.println(currentPath);
return;
}

{
if (!beingVisited[i])
{
dfs(i, d, beingVisited, currentPath);
currentPath.remove(i);
}
}

beingVisited[u] = false;
}``````
• Notice that that after processing each node we are not marking them as "visited" because our goal is to find all paths between two nodes, so an already visited node can be visited again if that constitutes an unique path between the two nodes.

It's important to note that, in general, we use "visited" flag to avoid visiting an already visited node again and again,
we use "visiting" flag to avoid cycle.

Only curious readers feel free to read the rest of this article. Till now I have always found myself using the above DFS approach when it comes to finding all paths between two nodes.

Using BFS:
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
```
```                ```
// C++ Implementation
// utility function for printing the found path in graph
void printpath(vector& 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& 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 >&g, int src, int dst, int v)
{
// create a queue which stores the paths
queue<vector> q;

// path vector to store the current path
vector path;
path.push_back(src);
q.push(path);
while (!q.empty()) {
path = q.front();
q.pop();
int last = path[path.size() - 1];

// if last vertex is the desired destination then print the path
if (last == dst)
printpath(path);

// 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 newpath(path);
newpath.push_back(g[last][i]);
q.push(newpath);
}
}
}
}
``````

My suggestion would be to have a very clear understanding of the DFS approach for finding all paths between two nodes in a graph discussed above as it is much simpler to understand than the BFS approach, can be implemented in less number of lines of code and in less time, and is efficient.

#### The above content is written by: 