Floyd-Warshall Algorithm: Shortest path between all pair of nodes

Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

Algorithm
Complexity
Implementations
Applications
Discussions

Reading time: 15 minutes | Coding time: 5 minutes

Floyd-Warshall 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 Floyd-Warshall Algorithm goes to Robert Floyd, Bernard Roy and Stephen Warshall.

floyd-1

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 and j, 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

Floyd-Warshal()
	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 all-pairs 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, .. k-1} 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
	 *
	 *  A--1--B
	 *  |    /
	 *  3   /
	 *	|  1
	 *  | /
	 *	C--2--D
	 *
	 * 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, .. k-1} 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
 A--1--B
 |    /
 3   /
 |  1
 | /
 C--2--D
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