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

#### graph algorithm floyd warshall algorithm dynamic programming shortest path

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.

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] = inf 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
}
}
}
// 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("\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
*/
{  0,   1, 3, INF},
{  1,   0, 1, INF},
{  3,   1, 0,   2},
{INF, INF, 2,   0}
};
}


### 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
# 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
# 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();
"""
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
"""
[  0,   1, 3, INF],
[  1,   0, 1, INF],
[  3,   1, 0,   2],
[INF, INF, 2,   0]
]


### Applications

The applications of Floyd Warshall Algorithm is as follows:

• Detecting the Presence of a Negative Cycle

• Transitive Closure of a Directed Graph

#### Alexa Ryder

Hi, I am creating the perfect textual information customized for learning. Message me for anything.