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