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:

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