Shortest path in an unweighted graph in Python with Diagram
In this blog, we’ll see how we can find the shortest path in an unweighted graph in Python.
Ex:
Now there are many ways you can tackle this problem. You can use the Bellman-Ford algorithm with all the edge weights as same. For that matter, you can use any shortest path algorithm. But the most time-efficient method to use here is BFS which can solve this problem in O(V+E).
Idea:
Our idea is to do BFS from our source vertex while storing the predecessor. For each node at each step, we store the distance to each vertex from the source which would just be the level of that vertex from the source.
If we reach our destination vertex we break out of the loop and return our parent array which we can use to construct the path.
In the BFS, we start with a vertex and visit all the vertices reachable from this vertex. The distance to all of these vertices is increased by one(this is kinda the same concept as a level). We continue this until all of the vertices are visited.
Here we are covering all the neighbors of a vertex and only after its completion we move on to the next level. Therefore we are sure to get the Shortest path in an unweighted graph.
class Graph: def __init__(self,V): self.V = V self.Graph = {} def addEdge(self,start,dest): if(start not in list(self.Graph.keys())): self.Graph[start] = [] if(dest not in list(self.Graph.keys())): self.Graph[dest] = [] #Creating an undirected Graph self.Graph[start].append(dest) self.Graph[dest].append(start) def BFS(self,root,dest): queue = [root] explored = [] parent = {root: -1} distance = {root : 0} while(queue): curr = queue.pop(0) if(dest == curr): return parent explored.append(curr) for v in self.Graph[curr]: if(v not in explored): parent[v] = curr distance[v] = distance[curr] + 1 queue.append(v) if(v == dest): return parent return [] def PrintShortestPath(self,root,dest): sol = self.BFS(root,dest) if(not sol): print("There is no path from source to the destination") else: temp = dest while(sol[temp] != -1): print(str(temp) + "->",end="") temp = sol[temp] print(str(root),end="") g = Graph(8) g.addEdge(1,2) g.addEdge(2,3) g.addEdge(3,4) g.addEdge(3,5) g.addEdge(3,7) g.addEdge(3,8) g.addEdge(5,7) g.addEdge(5,6) g.addEdge(6,7) g.addEdge(7,8) print() print("Below are the shortest path for different destinations") for i in range(1,9): print("Path from 1 to " + str(i) + ": ",end="") g.PrintShortestPath(1,i) print()
Output: Below are the shortest path for different destinations Path from 1 to 1: 1 Path from 1 to 2: 2->1 Path from 1 to 3: 3->2->1 Path from 1 to 4: 4->3->2->1 Path from 1 to 5: 5->3->2->1 Path from 1 to 6: 6->5->3->2->1 Path from 1 to 7: 7->3->2->1 Path from 1 to 8: 8->3->2->1
Leave a Reply