Print all paths from a given source to a destination in Python

In this article, we will learn how to print all the paths from a given source to a destination in Python.

We have given a graph, source vertex, and destination vertex.

This problem also commonly known as “Print all paths between two nodes”.

Example:

Depth First Search

• First, start with the source vertex ‘s’ and move to the next vertex.
• We observe the new problem is to find the route from the current vertex to the destination.
• We need to keep an eye on the visited nodes to avoid cycles.
• Add the current vertex to the result to keep track of the path from the source.
• Print the route when you reach the destination.
• Now go to the next node in the adjacent list in step 1 and repeat all the steps (loop)

For more understanding see the code below:

#Python program for Depth First Search

from collections import defaultdict 
   
#This class shows a directed graph 
 
class Graph: 
   
    def __init__(self,vertices): 

        self.V= vertices  
          
        
        self.graph = defaultdict(list)  
   
    #this function adds an edge to the graph 
    def addEdge(self,u,v): 
        self.graph[u].append(v) 
   

    def printAllPathsUtil(self, u, d, visited, path): 
  
        # checking all the visited nodes 
        visited[u]= True
        path.append(u) 
  
        if u ==d: 
            print path 
        else: 
            
            for i in self.graph[u]: 
                if visited[i]==False: 
                    self.printAllPathsUtil(i, d, visited, path) 
                      
        path.pop() 
        visited[u]= False
   
   
    # Printing all paths from sourse to destination
 
    def printAllPaths(self,s, d): 
  
        #Marking all the vertices as not visited 
        visited =[False]*(self.V) 
  
        #Create an array to store paths 
        path = [] 
  
        #Calling a recursive function for printing all paths 
        self.printAllPathsUtil(s, d,visited, path) 
   
   
#Creating a graph as shown in the above figure
   
g = Graph(4) 
g.addEdge(0, 1) 
g.addEdge(0, 2) 
g.addEdge(0, 3) 
g.addEdge(2, 0) 
g.addEdge(2, 1) 
g.addEdge(1, 3) 
   
s = 2 ; d = 3
print (" These are the all unique paths from node %d to %d : " %(s, d)) 
g.printAllPaths(s, d)

Output:

These are the all unique paths from node 2 to 3
2 0 1 3
2 0 3
2 1 3

Also read: How to implement Dijkstra’s shortest path algorithm in Python

2 responses to “Print all paths from a given source to a destination in Python”

1. Leandro says:

   October 31, 2020 at 12:19 pm

   Thanks for your post. I was only checking your post that I could implement it on my graph structure using linkedlist (not graph built in). Part of my assignment in my postgrad DSA unit. Thank you so much. Hope I can write a blog to help others too.

   Reply
   • Saruque Ahamed Mollick says:

     October 31, 2020 at 8:25 pm

     You can definitely write blog for us. Just click on the contact button and ask for it.

     Reply