1. In all pair shortest path, when a weighted graph is represented by its weight matrix W then objective is to find the distance between every pair of nodes.
2. We will apply dynamic programming to solve the all pairs shortest path.
3. In all pair shortest path algorithm, we first decomposed the given problem into sub problems.
4. In this principle of optimally is used for solving the problem.
5. It means any sub path of shortest path is a shortest path between the end nodes.

Steps:

i. Let $A^k_{i, j}$ be the length of shortest path from node i to node j such that the label for every intermediate node will be ≤ k.

ii. Now, divide the path from i node to j node for every intermediate node, say ‘k’ then there arises two case.

a. Path going from i to j via k. b. Path which is not going via k.

iii. Select only shortest path from two cases.

iv. Using recursive method we compute shortest path.

v. Initially: $A^0 = W [i, j]$

vi. Next computations: $A^k_{i, j} = min { A^{k-1}_{i, j}, A^{k-1}_{i, k}, A^{k-1}_{k, j}}$

Algorithm:

Analysis of Algorithm:

i. The first double for loop takes O (n2) time.

ii. The nested three for loop takes O (n3) time.

iii. Thus, the whole algorithm takes O (n3) time.

Example: Compute all pair shortest path for following figure 7.

Solution:

Thus the shortest distances between all pair are obtained.