# 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”

### Leave a Reply

You must be logged in to post a comment.

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.

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