Finding All Paths Between Two Nodes in A Graph

Algorithms and Data Structures: TheAlgorist.com

System Design: www.System.Design

Low Level Design: LowLevelDesign.io

Frontend Engineering: FrontendEngineering.io
জয় শ্রী রাম
🕉
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:
// Method to print all paths between two nodes using DFS approach. // Graph is represented as Adjacency List. // Total number of nodes = n. // So, n = adjacencyList.size() // Nodes are marked from 0 to (n  1) // Adjacency List will contain entries for all nodes, if a node // has no adjacent node, then the adjacency list will contain an empty list for that node. public void printAllPaths(List<List<Integer>> adjacencyList, int source, int destination) { boolean[] beingVisited = new boolean[adjacencyList.size()]; List<Integer> currentPath = new ArrayList<>(); currentPath.add(source); dfs(adjacencyList, source, destination, beingVisited, currentPath); } private void dfs(List<List<Integer>> graph, int source, int destination, boolean[] beingVisited, List<Integer> currentPath) { if (source == destination) { printPath(currentPath); // TODO: implement method to print the path return; } beingVisited[source] = true; // to avoid cycle for (Integer i : graph.get(source)) // loop over all adjacent nodes { if (!beingVisited[i]) { currentPath.add(i); dfs(graph, i, destination, beingVisited, currentPath); currentPath.remove(i); } } beingVisited[source] = false; }
Python:
# Method to print all paths between two nodes using DFS approach. # Graph is represented as Adjacency List. # Total number of nodes = n. # So, n = adjacencyList.size()// Nodes are marked from 0 to (n  1) # Adjacency List will contain entries for all nodes, if a node # has no adjacent node, then the adjacency list will contain an empty list def printAllPaths(self, adjacencyList, source, destination): beingVisited = [False for _ in range(len(adjacencyList))] currentPath = [] currentPath.append(source) self._dfs(adjacencyList, source, destination, beingVisited, currentPath) def _dfs(self, graph, source, destination, beingVisited, currentPath): if source == destination: printPath(currentPath) # TODO: implement method to print the path return beingVisited[source] = True # to avoid cycle for i in graph[source]: # loop over all adjacent nodes if not beingVisited[i]: currentPath.append(i) self._dfs(graph, i, destination, beingVisited, currentPath) currentPath.pop(i) beingVisited[source] = 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.
Using BFS:
Below code is selfexplanatory and I have put the critical parts of the algorithms in the comment.
Java:
// Print All Paths from Source to Destination. // Note that graph is represented as adjacency list. // Approach used: Breadth First Search (BFS) private void findPaths(List<List<Integer>> adjacencyList, int source, int destination) { Queue<List<Integer> > bfsQueue = new LinkedList<>(); List<Integer> path = new ArrayList<>(); path.add(source); // path always begins with the source bfsQueue.offer(path); while (!bfsQueue.isEmpty()) { path = bfsQueue.poll(); int last = path.get(path.size()  1); // If destination node is reached or found // then print the path if (last == destination) { printPath(path); // TODO: implement this method } List<Integer> adjacentNodes = adjacencyList.get(last); for(int i = 0; i < adjacentNodes.size(); i++) { if (!path.contains(adjacentNodes.get(i))) // avoid infinite loop: do not visit already visited node { List<Integer> newPartialPath = new ArrayList<>(path); // new partial path found that might potentially lead to the destination newPartialPath.add(adjacentNodes.get(i)); bfsQueue.offer(newPartialPath); } } } }