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

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

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

1. Leandro says:

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.

• Saruque Ahamed Mollick says:

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