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.
                    
        // 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;
        }
  • 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 self-explanatory and I have put the critical parts of the algorithms in the comment.

                        
    
        // 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);
                    }
                }
            }
        }
    
                        


Instructor:

Abhishek Dey

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

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave