FloydWarshall Algorithm: Shortest path between all pair of nodes
Sign up for FREE 1 month of Kindle and read all our books for free.
Get FREE domain for 1st year and build your brand new site
Reading time: 15 minutes  Coding time: 5 minutes
FloydWarshall Algorithm is an algorithm based on dynamic programming technique to compute the shortest path between all pair of nodes in a graph.
The credit of FloydWarshall Algorithm goes to Robert Floyd, Bernard Roy and Stephen Warshall.
Limitations:
 The graph should not contain negative cycles.
 The graph can have positive and negative weight edges.
For a graph with vertices:
 Initialize the shortest paths between any 2 vertices with
Infinity
(INT.maximum).  Find all pair shortest paths that use 0 intermediate vertices, then find the shortest paths that use 1 intermediate vertex and so on, until using all N vertices as intermediate nodes.
 Minimize the shortest paths between any pairs in the previous operation.
 For any 2 vertices
i
andj
, one should actually minimize the distances between this pair using the first K nodes, so the shortest path will be:minimum( D[i][k] + D[k][j], D[i][j])
.
Pseudocode
FloydWarshal()
d[v][u] = infinity for each pair (v,u)
d[v][v] = 0 for each vertex v
for k = 1 to n
for i = 1 to n
for j = 1 to n
d[i][j] = min(d[i][j], d[i][k] + d[k][j])
Complexity
 Worst case time complexity:
Î˜(V^3)
 Average case time complexity:
Î˜(V^3)
 Best case time complexity:
Î˜(V^3)
 Space complexity:
Î˜(V^2)
Implementations
Implementation of Floyd Warshall algorithm in 4 languages that includes C
, C++
, Java
and Python
.
 C
 C++
 Java
 Python
C
// C Program for Floyd Warshall Algorithm
// Part of Cosmos by OpenGenus Foundation
#include<stdio.h>
// Number of vertices in the graph
#define V 4
/* Define Infinite as a large enough value. This value will be used
for vertices not connected to each other */
#define INF 99999
// A function to print the solution matrix
void printSolution(int dist[][V]);
// Solves the allpairs shortest path problem using Floyd Warshall algorithm
void floydWarshall (int graph[][V]) {
/* dist[][] will be the output matrix that will finally have the shortest
distances between every pair of vertices */
int dist[V][V], i, j, k;
/* Initialize the solution matrix same as input graph matrix. Or
we can say the initial values of shortest distances are based
on shortest paths considering no intermediate vertex. */
for (i = 0; i < V; i++) {
for (j = 0; j < V; j++) {
dist[i][j] = graph[i][j];
}
}
/* Add all vertices one by one to the set of intermediate vertices.
> Before start of a iteration, we have shortest distances between all
pairs of vertices such that the shortest distances consider only the
vertices in set {0, 1, 2, .. k1} as intermediate vertices.
> After the end of a iteration, vertex no. k is added to the set of
intermediate vertices and the set becomes {0, 1, 2, .. k} */
for (k = 0; k < V; k++) {
// Pick all vertices as source one by one
for (i = 0; i < V; i++) {
// Pick all vertices as destination for the
// above picked source
for (j = 0; j < V; j++) {
// If vertex k is on the shortest path from
// i to j, then update the value of dist[i][j]
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
// Print the shortest distance matrix
printSolution(dist);
}
/* A utility function to print solution */
void printSolution(int dist[][V]) {
printf ("Following matrix shows the shortest distances"
" between every pair of vertices \n");
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] == INF)
printf("%7s", "INF");
else
printf ("%7d", dist[i][j]);
}
printf("\n");
}
}
// driver program to test above function
int main() {
/* Let us create the following weighted graph
10
(0)>(3)
 /\
5  
  1
\/ 
(1)>(2)
3 */
int graph[V][V] = { {0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}
};
// Print the solution
floydWarshall(graph);
return 0;
}
C++
/* Part of Cosmos by OpenGenus Foundation */
#include <cstdio>
#include <algorithm>
using namespace std;
#define INF 1000000000
void floydWarshall(int vertex, int adjacencyMatrix[][4]) {
// calculating all pair shortest path
for(int k = 0; k < vertex; k++) {
for(int i = 0; i < vertex; i++) {
for(int j = 0; j < vertex; j++) {
// relax the distance from i to j by allowing vertex k as intermediate vertex
// consider which one is better, going through vertex k or the previous value
adjacencyMatrix[i][j] = min( adjacencyMatrix[i][j], adjacencyMatrix[i][k] + adjacencyMatrix[k][j] );
}
}
}
// pretty print the graph
printf("o/d"); // o/d means the leftmost row is the origin vertex
// and the topmost column as destination vertex
for(int i = 0; i < vertex; i++) {
printf("\t%d", i+1);
}
printf("\n");
for(int i = 0; i < vertex; i++) {
printf("%d", i+1);
for(int j = 0; j < vertex; j++) {
printf("\t%d", adjacencyMatrix[i][j]);
}
printf("\n");
}
}
int main() {
/*
* input is given as adjacency matrix,
* input represents this undirected graph
*
* A1B
*  /
* 3 /
*  1
*  /
* C2D
*
* should set infinite value for each pair of vertex that has no edge
*/
int adjacencyMatrix[][4] = {
{ 0, 1, 3, INF},
{ 1, 0, 1, INF},
{ 3, 1, 0, 2},
{INF, INF, 2, 0}
};
floydWarshall(4, adjacencyMatrix);
}
Java
import java.util.*;
import java.lang.*;
import java.io.*;
// Part of Cosmos by OpenGenus Foundation
class FloydWarshall{
final static int INF = 99999, V = 4;
void floydWarshall(int graph[][])
{
int dist[][] = new int[V][V];
int i, j, k;
/* Initialize the solution matrix same as input graph matrix.
Or we can say the initial values of shortest distances
are based on shortest paths considering no intermediate
vertex. */
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
dist[i][j] = graph[i][j];
/* Add all vertices one by one to the set of intermediate
vertices.
> Before start of a iteration, we have shortest
distances between all pairs of vertices such that
the shortest distances consider only the vertices in
set {0, 1, 2, .. k1} as intermediate vertices.
> After the end of a iteration, vertex no. k is added
to the set of intermediate vertices and the set
becomes {0, 1, 2, .. k} */
for (k = 0; k < V; k++)
{
// Pick all vertices as source one by one
for (i = 0; i < V; i++)
{
// Pick all vertices as destination for the
// above picked source
for (j = 0; j < V; j++)
{
// If vertex k is on the shortest path from
// i to j, then update the value of dist[i][j]
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
// Print the shortest distance matrix
printSolution(dist);
}
void printSolution(int dist[][])
{
System.out.println("Following matrix shows the shortest "+
"distances between every pair of vertices");
for (int i=0; i<V; ++i)
{
for (int j=0; j<V; ++j)
{
if (dist[i][j]==INF)
System.out.print("INF ");
else
System.out.print(dist[i][j]+" ");
}
System.out.println();
}
}
// Driver program to test above function
public static void main (String[] args)
{
/* Let us create the following weighted graph
10
(0)>(3)
 /\
5  
  1
\/ 
(1)>(2)
3 */
int graph[][] = { {0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}
};
FloydWarshall a = new FloydWarshall();
// Print the solution
a.floydWarshall(graph);
}
}
Python
''' Part of Cosmos by OpenGenus Foundation '''
INF = 1000000000
def floyd_warshall(vertex, adjacency_matrix):
# calculating all pair shortest path
for k in range(0, vertex):
for i in range(0, vertex):
for j in range(0, vertex):
# relax the distance from i to j by allowing vertex k as intermediate vertex
# consider which one is better, going through vertex k or the previous value
adjacency_matrix[i][j] = min(adjacency_matrix[i][j], adjacency_matrix[i][k] + adjacency_matrix[k][j])
# pretty print the graph
# o/d means the leftmost row is the origin vertex
# and the topmost column as destination vertex
print("o/d", end='')
for i in range(0, vertex):
print("\t{:d}".format(i+1), end='')
print();
for i in range(0, vertex):
print("{:d}".format(i+1), end='')
for j in range(0,vertex):
print("\t{:d}".format(adjacency_matrix[i][j]), end='')
print();
"""
input is given as adjacency matrix,
input represents this undirected graph
A1B
 /
3 /
 1
 /
C2D
should set infinite value for each pair of vertex that has no edge
"""
adjacency_matrix = [
[ 0, 1, 3, INF],
[ 1, 0, 1, INF],
[ 3, 1, 0, 2],
[INF, INF, 2, 0]
]
floyd_warshall(4, adjacency_matrix);
Applications
The applications of Floyd Warshall Algorithm is as follows:

Detecting the Presence of a Negative Cycle

Transitive Closure of a Directed Graph