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.

All pair shortest path floyd warshall algorithm

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))

#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³).



Related Contents to follow