🙏

জয়  শ্রী  রাম

🕉

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 self-explanatory 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);
                  }
              }
          }
      }
  
                      

Instructor:

Abhishek Dey

Senior SDE | Chief Architect

AWS | Microsoft | University of Florida

View LinkedIn profile