Number of shortest paths in an unweighted and directed graph in Python

In this tutorial, we’ll learn how to find the number of shortest paths in an unweighted and directed graph in Python.

Here’s what an unweighted directed graph looks like:

There are two graph traversal techniques – BFS and DFS. As BFS (Breadth-First Search) is more efficient than DFS (Depth-first Search ), we’ll employ BFS.

PROCEDURE

Two arrays namely – distancE[] and patH[] are used. distancE[] stores the shortest distance from source vertex to the destination vertex. patH[] stores the number of different paths from the source vertex to different vertices in the graph.

The elements in distancE[] are initially set to infinity, except source vertex which is set to 0. The elements in patH[] are initially 0, except source vertex which is equal to 1, because every vertex has a single shortest path to itself. BFS traversal of the graph :

For every neighbor V2 of each vertex V1 :

• if distancE[V1] > distancE[V2]+1 ,then decrease the distancE[V1] to distancE[V2] +1 and then assign number of paths of vertex V1 to that of vertex V2.
• else if distancE[V2] = distancE[V2] + 1,  then simply add the number of paths of vertex V1 to the that of vertex V2.

Python Code:

The following code is an implementation of the given procedure. It has 10 vertices (nV=10).

#importing appropriate python libraries
from sys import maxsize as Maxi
from collections import deque 

#Traversing a graph using BFS and computing distancE[] and patH[]
def Bfs_traversaL(adjacenT: list, sourcE: int, distancE: list, patH: list, nV: int): 
    visited = [False] *nV
    distancE[sourcE] = 0
    patH[sourcE] = 1

    P = deque() 
    P.append(sourcE) 
    visited[sourcE] = True
    while P: 
        current_verteX = P[0] 
        P.popleft() 

#loop to check all neighbouring vertices of current_verteX 
        for x in adjacenT[current_verteX]: 
# Is the current_verteX is not yet visited?
#let's push it to our Queue         
            if not visited[x]:    

                P.append(x) 
                visited[x] = True

# Is there a better path?
            if distancE[x] > distancE[current_verteX] + 1:
                distancE[x] = distancE[current_verteX] + 1
                patH[x] = patH[current_verteX] 

# Found another shortest path?
            elif distancE[x] == distancE[current_verteX] + 1: 
                patH[x] += patH[current_verteX] 

#computing shortest path form given vertex_s
    #nV : number of vertices

def Looking_for_shortest_path(adjacenT: list, Vertex_s: int, nV: int): 
    distancE = [Maxi] *nV
    patH = [0] *nV
    Bfs_traversaL(adjacenT, Vertex_s, distancE, patH, nV) 
    print("What is the number of shortest paths for an unweighted and directed graph with ",nV, "vertices?")
    print("* * * * * * *")
    print("Number of shortest paths", end=" ")  
    for i in patH: 
        print(i, end=" ") 

def add_new_edgE(adjacenT: list, u: int, v: int):
    adjacenT[u].append(v) 

if __name__ == "__main__": # Main section
    nV= 10
    adjacenT = [0] *nV
    for i in range(nV): 
        adjacenT[i] = [] 

    add_new_edgE(adjacenT, 0, 1) 
    add_new_edgE(adjacenT, 0, 2) 
    add_new_edgE(adjacenT, 1, 2) 
    add_new_edgE(adjacenT, 1, 3) 
    add_new_edgE(adjacenT, 2, 3)
    add_new_edgE(adjacenT, 3, 4) 
    add_new_edgE(adjacenT, 3, 5) 
    add_new_edgE(adjacenT, 4, 6) 
    add_new_edgE(adjacenT, 5, 6)
    add_new_edgE(adjacenT, 6, 7)
    add_new_edgE(adjacenT, 6, 8)
    add_new_edgE(adjacenT, 7, 9)

    Looking_for_shortest_path(adjacenT, 0, 10)

Output for Number of shortest paths:

The output looks as follows:

What is the number of shortest paths for an unweighted and directed graph with 10 vertices?
* * * * * * *
Number of shortest paths 1 1 1 2 2 2 4 4 4 4

Time complexity: O(V+E).

For further reference regarding python syntaxes, concepts and methods, kindly visit the Collections Module in Python, sys Module in Python with Examples