C++ Program to Implement Floyd Warshall Algorithm

Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles). A single execution of the algorithm will find the lengths (summed weights) of the shortest paths between all pairs of vertices, though it does not return details of the paths themselves.

Pseudo code:

let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each vertex v
   dist[v][v] ← 0
for each edge (u,v)
   dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
for k from 1 to |V|
   for i from 1 to |V|
      for j from 1 to |V|
         if dist[i][j] > dist[i][k] + dist[k][j]
            dist[i][j] ← dist[i][k] + dist[k][j]
         end if

 

Example:

Floyd Warshall algorithm

 

Prior to the first iteration of the outer loop, labeled k=0 above, the only known paths correspond to the single edges in the graph. At k=1, paths that go through the vertex 1 are found: in particular, the path 2→1→3 is found, replacing the path 2→3 which has fewer edges but is longer. At k=2, paths going through the vertices {1,2} are found. The red and blue boxes show how the path 4→2→1→3 is assembled from the two known paths 4→2 and 2→1→3 encountered in previous iterations, with 2 in the intersection. The path 4→2→3 is not considered, because 2→1→3 is the shortest path encountered so far from 2 to 3. At k=3, paths going through the vertices {1,2,3} are found. Finally, at k=4, all shortest paths are found.

C++ program to implement Floyd Warshall Algorithm:

#include <iostream>
using namespace std;

void floyds(int b[][7])
{
    int i, j, k;
    for (k = 0; k < 7; k++)
    {
        for (i = 0; i < 7; i++)
        {
            for (j = 0; j < 7; j++)
            {
                if ((b[i][k] * b[k][j] != 0) && (i != j))
                {
                    if ((b[i][k] + b[k][j] < b[i][j]) || (b[i][j] == 0))
                    {
                        b[i][j] = b[i][k] + b[k][j];
                    }
                }
            }
        }
    }
    for (i = 0; i < 7; i++)
    {
        cout<<"nMinimum Cost With Respect to Node:"<<i<<endl;
        for (j = 0; j < 7; j++)
        {
            cout<<b[i][j]<<"t";
        }
    }
}
int main()
{
        int b[7][7];
        cout<<"ENTER VALUES OF ADJACENCY MATRIXnn";
        for (int i = 0; i < 7; i++)
        {
                cout<<"enter values for "<<(i+1)<<" row"<<endl;
                for (int j = 0; j < 7; j++)
                cin>>b[i][j];
        }
        floyds(b);
        return 0;
}

OUTPUT:

ENTER VALUES OF ADJACENCY MATRIX

enter values for 1 row
0
3
6
0
0
0
0
enter values for 2 row
3
0
2
4
0
0
0
enter values for 3 row
6
2
0
1
4
2
0
enter values for 4 row
0
4
1
0
2
0
4
enter values for 5 row
0
0
4
2
0
2
1
enter values for 6 row
0
0
2
0
2
0
1
enter values for 7 row
0
0
0
4
1
1
0

Minimum Cost With Respect to Node:0
0       3       5       6       8       7       8
Minimum Cost With Respect to Node:1
3       0       2       3       5       4       5
Minimum Cost With Respect to Node:2
5       2       0       1       3       2       3
Minimum Cost With Respect to Node:3
6       3       1       0       2       3       3
Minimum Cost With Respect to Node:4
8       5       3       2       0       2       1
Minimum Cost With Respect to Node:5
7       4       2       3       2       0       1
Minimum Cost With Respect to Node:6
8       5       3       3       1       1       0

Leave a Reply