All Pair Shortest Path Problem in Python

The All Pair Shortest Path Problem is about finding a path between each and every vertex to all other vertices in a graph such that the total distance between them is minimum.

The Floyd Warshall Algorithm is used for solving the All Pairs Shortest Path problem. We implement this by finding the shortest path between every pair of vertices in a given weighted directed graph.

For Example,

• There exists five offices in five different cities.
• The cost of travel between each pair of cities is known.
• We have to find the cheapest way to reach each office from every other office.

Floyd Warshall Algorithm to solve All Pair Shortest Path Problem

The Floyd-Warshall Algorithm is an algorithm for finding the shortest path between all the pairs of vertices in a weighted graph. This algorithm can be applied to both directed and undirected weighted graphs.

However, the Floyd-Warshall Algorithm does not work with graphs having negative cycles. Floyd-Warshall Algorithm follows the dynamic programming approach to find the shortest paths.

Note: A graph can have positive as well as negatively weighted edges. A negative cycle is one in which the overall sum of the cycle becomes negative.

Implementation of Floyd-Warshall Algorithm

For the implementation of the Floyd-Warshall Algorithm, we create the floydWarshall method that takes two parameters as input – the number of vertices and a reference to the graph data structure.

The Floyd-Warshall Algorithm is based on the following steps:

• We are given a weighted directed or undirected graph.
• We create a matrix of size N*N where N is the number of vertices of the graph. Let this matrix be called A.
• The value of the A[i][j] cell is the weight of the direct path between the ith and jth nodes of the graph. If no direct path exists between two vertices, set their distance infinity for the moment.
• Now we iterate over each pair of nodes in the matrix and reduce the paths to the shortest distance.
• This process is repeated until all pairs of nodes are assigned their desiredd path lengths.

#Function to implement Floyd-Warshall Algorithm
INF = 9999
def printSolution(numOfVertices, distance):
    for i in range(numOfVertices):
        for j in range(numOfVertices):
            if(distance[i][j] == INF):
                print("INF", end=" ")
            else:
                print(distance[i][j], end="  ")
        print(" ")

def floydWarshall(numOfVertices, G):
    distance = G
    for k in range(numOfVertices):
        for i in range(numOfVertices):
            for j in range(numOfVertices):
                distance[i][j] = min(
                    distance[i][j], distance[i][k]+distance[k][j])

    printSolution(numOfVertices, distance)


G = [[0, 8, INF, 1],
     [INF, 0, 1, INF],
     [4, INF, 0, INF],
     [INF, 2, 9, 1]
     ]

floydWarshall(4, G)

Output

Time and Space Complexity

The time complexity for the Floyd-Warshall Algorithm is O(V^3) because we use three nested for loops, each iterating over all the vertices of the graph. The space complexity is O(V^2) because we store all pairs of nodes in a temporary matrix.

BFS vs Dijkstra vs Bellman-Ford vs Floyd-Warshall

Graph Type	BFS	Dijkstra	Bellman-Ford	Floyd-Warshall
Unweighted-undirected	OK	OK	OK	OK
Unweighted-directed	OK	OK	OK	OK
Positive-weighted-undirected	X	OK	OK	OK
Positive-weighted-directed	X	OK	OK	OK
Negative-weighted-undirected	X	OK	OK	OK
Negative-weighted-directed	X	OK	OK	OK
Negative Cycle	X	X	OK	X