Finding All Paths Between Two Nodes in A Graph

Customer Support: admin@thealgorists.com

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.
 If you are a student, email to admin@thealgorists.com to get special student discount.
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<>(); currentPath.add(s); 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; } for (Integer i : adjList[u]) { if (!beingVisited[i]) { currentPath.add(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:
Abhishek Dey
A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More
Microsoft  University of Florida
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn