# All pair shortest path floyd warshall algorithm

*All pair shortest path floyd warshall algorithm. All pair shortest path is problem of finding shortest distance between every pair of vertices/nodes in a given directed weighted graph. floyd warshall algorithm is an algorithm which finds shortest path between every pair of vertices/nodes in a given directed weighted graph. The weight can be positive or negative. The only constrains of this algorithm is “graph should not contain a negative cycle“. Negative cycle is a cycle whose sum of edge weights is negative.*

*Let us take an example graph ( below figure). The right side is representation of graph as matrix. The distance or weight of an edge is the cell value. For example in below graph the distance/weight between node 1 to node 2 is 6 so in matrix C¹²=6. If the two nodes are unreachable then the distance between them will be infinity, for example in below graph there is no direction from 1 to 4 so distance between them would be infinity, however there is direction from 4 to 1 and distance is 2. *

*The Floyd-Warshall Algorithm*

*This algorithm calculates the length of the shortest path between every pair of nodes in a graph in O(V3) time.*

*(1) Take a matrix of size (NXN) where N is number of vertices/nodes.*

*(2) Initialize all distances between nodes (i,j) to INF. take very large value to INF=INT_MAX.*

*(3) Fill the distance between nodes (i,j) in matrix. ( this is also called adjacency matrix for graph representation)*

*(4) calculate all pairs shortest path by iterating*

* for i,j,k*

* distance (i,j) = min(( min(i,j) , mimI(i,j) + min(k,j))*

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include<stdio.h> #include<limits.h> // Number of V in the graph #define V 5 /* Define Infinite as a large enough value.*/ #define INF 88888 int main () { // Initialize distance INF //value of G[i][j] is distance from ith node to jth node // and feed the distance int G[V][V] = { {0, 6, 8, INF, -4}, {INF, 0, INF, 1, 7}, {INF, 4, 0, INF, INF}, {2, INF, -5, 0, INF}, {INF, INF, INF, 3, 0}}; int k = 0; int i = 0; int j = 0; // Floyd-Warshall // Add V in sequence // for example (add node 1 then 2, 3 upto n) and choose // shorter distance for (k = 0; k < V; k++) for (i = 0; i < V; i++) for (j = 0; j < V; j++) if (G[i][j] > G[i][k] + G[k][j]) G[i][j] = G[i][k] + G[k][j]; // Print out final distance matrix printf ("shortest distances between every pair of vertices\n"); for (i = 0; i < V; i++) { for (j = 0; j < V; j++) printf ("%5d", G[i][j]); printf ("\n"); } return 0; } |

**Time complexity O(N³).**

## Leave a Reply