In the last section, we discussed regarding shortest path algorithm that starts with a single source and determines shortest path to all vertices in the graph. In this section, we will discuss the problem of finding shortest path among all pairs of vertices in a graph. This problem is helpful in finding distance among all pairs of cities in a road atlas. All pairs shortest paths problem is mother of all of the shortest paths problems.
In this algorithm, we shall represent the graph through adjacency matrix.
The weight of an edge Cij in an adjacency matrix representation of any directed graph is represented as follows
Given directed graph G = (V, E), where each edge (v, w) contain a non-negative cost C(v , w), for all of the pairs of vertices (v, w) to determine the lowest cost path from v to w.
The All pairs shortest paths problem can be considered as a generalisation of single- source-shortest-path problem, using Dijkstra's algorithm by varying the source node amongst all the nodes in the graph. If negative edge(s) is allowed, then we can't employ Dijkstra's algorithm.
In this segment we will employ a recursive solution to all pair shortest paths problem known as Floyd-Warshall algorithm, which runs in O(n3) time.
This algorithm is depends on the following principle. For graph G let V = {1, 2,3,...,n}.Let us assume a sub set of the vertices {1, 2, 3, .....,k. For any pair of vertices which belong to V, assume all paths from i to j whose intermediate vertices are from {1, 2, 3, ....k}. This algorithm will exploit the relationship among path p and shortest path from i to j whose intermediate vertices are from {1, 2, 3, ....k-1} with the given two possibilities:
1. If k is not any intermediate vertex in the path p, then all of the intermediate vertices of the path p are in {1, 2, 3, ....,k-1}. Therefore, shortest path from i to j along intermediate vertices in {1, 2, 3, ....,k-1} is also the shortest path from i to j along vertices in {1, 2, 3, ..., k}.
2. If k is intermediate vertex of the path p, we break down the path p in path p1 from vertex i to k and path p2 from vertex k to j. So, path p1 is the shortest path from i to k along with intermediate vertices in {1, 2, 3, ...,k-1}.
Throughout iteration process we determine the shortest path from i to j using only vertices (1, 2,3, ..., k-1} and in the next step, we determine the cost of using the kth vertex as an intermediate step. If this results into lower cost, then we store it.
After n iterations (all possible iterations), we determine the lowest cost path from i to j by using all vertices (if essential).
Notice the following:
Initialize the matrix
C[i][ j] = ∞ if (i, j) does not associate with E for graph G = (V, E)
Initially, D[i][j] = C[i][j]
We also term a path matrix P where P[i][j] holds intermediate vertex k on the least cost path from i to j which leads to the shortest path from i to j .