All pair shortest path floyd warshall algorithm. All pair shortest path is problem of finding shortest distance between every pair of vertices/nodes in a given directed weighted graph. floyd warshall algorithm is an algorithm which finds shortest path between every pair of vertices/nodes in a given directed weighted graph. The weight can be positive or negative. The only constrains of this algorithm is “graph should not contain a negative cycle“. Negative cycle is a cycle whose sum of edge weights is negative.

Let us take an example graph ( below figure). The right side is representation of graph as matrix. The distance or weight of an edge is the cell value. For example in below graph the distance/weight between node 1 to node 2 is 6 so in matrix C¹²=6. If the two nodes are unreachable then the distance between them will be infinity, for example in below graph there is no direction from 1 to 4 so distance between them would be infinity, however there is direction from 4 to 1 and distance is 2.

All pair shortest path floyd warshall algorithm

The Floyd-Warshall Algorithm

This algorithm calculates the length of the shortest path between every pair of nodes in a graph in O(V3) time.

(1) Take a matrix of size (NXN) where N is number of vertices/nodes.
(2) Initialize all distances between nodes (i,j) to INF. take very large value to INF=INT_MAX.
(3) Fill the distance between nodes (i,j) in matrix. ( this is also called adjacency matrix for graph representation)
(4) calculate all pairs shortest path by iterating
    for i,j,k
    distance (i,j) = min(( min(i,j) , mimI(i,j) + min(k,j))

Time complexity O(N³).