Question

4A. Solve the all pairs shortest path problem for the graph indicated by the weight matrix 5 in Fig. Q.4A 0 2 o0 1 8 6 0 3 2 00 00 00 0 4 00 oo 00 2 0 3 3 o0 00 00 0 Fig. Q.4A

Answer 1

Floyd warshall algorithm is used to solve all pair shortest path problem. it uses dynamic programming approach to solve APSP in the graph.

Algorithm

for k from 0 to |V|-1:
    for i from 0 to |V|-1:
        for j from 0 to |V|-1:
            if M[i][j] > M[i][k] + M[k][j]:
                M[i][j] = M[i][k] + M[k][j]

in each step kth vertex is taken as intermediate vertex and path will smaller cost is found out.

Initial step k=0 and Matrix is same as given in the question

Then loop runs for k=1 means taking 1st vertex as intermediate

matrix we get after this operation is considered as input for k=2 and so on.

CAUsers satsahib Documents\floyd apsp.cpp [Executing] - Dev-C++5.11 Eile Edit Search Yew Project Execute Tools 스Style Window Help Project Classes CAUserslsatsahib\Documents floyd apsp.exe or k- Following matrix shows the shortest distances between every pair of vertices 2 INF 14 4 INF INF INF INF INF 5 INF for k- 1 Following matrix shows the shortest distances between every pair of vertices 14 4 INF INF INF INF INF for k- 2 Following matrix shows the shortest distances between every pair of vertice:s 14 4 INF INF INF INF INF for k 3 Following matrix shows the shortest distances between every pair of vertice:s INF INF INF INF for k 4 Following matrix shows the shortest distances between every pair of vertice:s Compiler 1e -Output Size: 130.352 5390625 RİB - Compilation Time: 0.42s Line: 49 Col: 27 Sel: 0 Length: 2897 ^回确脈4x 4/18/2018 46 PM Type here to search |

so after k=4, we get a final matrix.