Question

Find the All-pair Shortest Path for the given graph using Floyd Warshall Algorithm. . 2 6 3 8 -5 5 3

Answer 1

In floyd warshall Algorithm we first initialise a 2-D distance array with all values as infinity. Then we put value of (i,j) as the weight between the edge of vertex i and j.

Hence the inital matrix is :

Now one by one pick all vertices and updates all shortest paths which include the picked vertex as an intermediate vertex in the shortest path.Let intermediate vertex be k. For all vertices (i, j) of the source and destination respectively, there are two possible cases.

• if k is not an intermediate vertex in shortest path from i to j. We don't change the value of distance[i][j].
• else We update the value of distance[i][j] as distance[i][k] + dist[k][j] if distance[i][j] > distance[i][k] + distance[k][j]

For k = 1, the matrix formed is :

$\begin{bmatrix} 0 & 6 & 8 & inf & -4\\ inf & 0 & inf & 1 & 7\\ inf & 4 & 0 & inf & inf\\ 2 & 8 & -5 & 0 & -2\\ inf & inf & inf & 3 & 0\\ \end{bmatrix}$

for k = 2 :

$\begin{bmatrix} 0 & 6 & 8 & 7 & -4\\ inf & 0 & inf & 1 & 7\\ inf & 4 & 0 & 5 & 11\\ 2 & 8 & -5 & 0 & -2\\ inf & inf & inf & 3 & 0\\ \end{bmatrix}$

for k = 3 :

$\begin{bmatrix} 0 & 6 & 8 & 7 & -4\\ inf & 0 & inf & 1 & 7\\ inf & 4 & 0 & 5 & 11\\ 2 & -1 & -5 & 0 & -2\\ inf & inf & inf & 3 & 0\\ \end{bmatrix}$

for k = 4:

$\begin{bmatrix} 0 & 6 & 2 & 7 & -4\\ 3 & 0 & -4 & 1 & -1\\ 7 & 4 & 0 & 5 & 3\\ 2 & -1 & -5 & 0 & -2\\ 5 & 2 & -2 & 3 & 0\\ \end{bmatrix}$

for k = 5:

$\begin{bmatrix} 0 & -2 & -6 & -1 & -4\\ 3 & 0 & -4 & 1 & -1\\ 7 & 4 & 0 & 5 & 3\\ 2 & -1 & -5 & 0 & -2\\ 5 & 2 & -2 & 3 & 0\\ \end{bmatrix}$

Matrix formed for k=5 is the final matrix.

So the cell (i,j) in the matrox as dicussed above shows the shortest distance between vertex i and j.

You can also find the c++ code for generating the final matrix through floyd warshall for your graph here : https://pastebin.com/2CLiShLr

to run the code give input as :

1 2 6
1 5 -4
5 4 3
4 3 -5
3 2 4
1 3 8
4 1 2
2 5 7
2 4 1

which is nothing but source destination weight for all edges in your case.