Shortest Path Using Breadth First Search (BFS)

Shortest Path Using Breadth First Search (BFS)

Here , To find the shortest path using BFS first we have to know that the graph should always be unweighted graph .

If you know about the BFS algorithm then to find shortest path we have to add only one thing that is a dictionary named "dist" which records the distance of every node from given node As shown in below code.

Code :

from collections import defaultdict # This class represents a directed graph # using adjacency list representation class Graph: # Constructor def __init__(self): # default dictionary to store graph self.graph = defaultdict(list) # function to add an edge to graph def addEdge(self,u,v): self.graph[u].append(v) # Function to print a BFS of graph def BFS(self, s): dist=[0]*10 # Mark all the vertices as not visited visited = [False] * (len(self.graph)) # Create a queue for BFS queue = [] # Mark the source node as # visited and enqueue it queue.append(s) visited[s] = True while queue: # Dequeue a vertex from # queue and print it s = queue.pop(0) print (s, end = " ") # Get all adjacent vertices of the # dequeued vertex s. If a adjacent # has not been visited, then mark it # visited and enqueue it for i in self.graph[s]: if visited[i] == False: dist[i]=dist[s]+1 queue.append(i) visited[i] = True print(dist) # Driver code # Create a graph given in # the above diagram g = Graph() g.addEdge(0, 1) g.addEdge(1,0) g.addEdge(0, 3) g.addEdge(3,0) g.addEdge(1, 2) g.addEdge(2,1) g.addEdge(3, 7) g.addEdge(7,3) g.addEdge(3, 4) g.addEdge(4,3) g.addEdge(4, 7) g.addEdge(7,4) g.addEdge(4, 6) g.addEdge(6,4) g.addEdge(7, 6) g.addEdge(6,7) g.addEdge(6, 5) g.addEdge(5,6) print ("Following is Breadth First Traversal" " (starting from vertex 2)") g.BFS(2)