• 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

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