Modify Floyds allpairs shortest paths algorithm so that k is

Modify Floyd’s all-pairs shortest paths algorithm so that k is varied in the innermost loop instead of the outermost. Consider the following weighted graph: V = {A, B, C, D} and E = {AB, BC, CD} with the weight of each edge being 1. Execute the modified algorithm on this matrix associated with this graph. Is the result the same as what Floyd’s algorithm would produce? Explain.

Solution

Answer:

Adjacency matrix for the given graph will be:

On using the original Flyod\'s algorithm, we will get the following shortest path weight matrix

Note: In original algorithm, k is varied in the outermost loop.

On modifying the Flyod\'s algorithm to vary k in the innermost loop, we get the following shortest path weight matrix:

From the result, it is evident that the result is different from that produced by original algorithm. This result is basically the ajacency matrix of given graph.

Explanation: This result is due to the fact that all possible options for intermediate vertices are not considered when k is varied in the innermost loop and only vertices directly connected to the concerned source vertex i.e. adjacent vertex (on edge) are considered. Thats why adjacency matrix is produced as the result in place of a valid shortest path weight matrix.