Floyd-Warshall Algorithm is an algorithm for finding the shortest path between all the pairs of vertices in a weighted graph. This algorithm works for both the directed and undirected weighted graphs. But, it does not work for the graphs with negative cycles (where the sum of the edges in a cycle is negative).
A weighted graph is a graph in which each edge has a numerical value associated with it.
Floyd-Warhshall algorithm is also called as Floyd's algorithm, Roy-Floyd algorithm, Roy-Warshall algorithm, or WFI algorithm.
How Floyd-Warshall Algorithm Works?
Let the given graph be:
Follow the steps below to find the shortest path between all the pairs of vertices.
- Create a matrix
A0of dimensionn*nwhere n is the number of vertices. The row and the column are indexed as i and j respectively. i and j are the vertices of the graph.
Each cell A[i][j] is filled with the distance from theithvertex to thejthvertex. If there is no path fromithvertex tojthvertex, the cell is left as infinity. - Now, create a matrix
A1using matrixA0. The elements in the first column and the first row are left as they are. The remaining cells are filled in the following way.
Let k be the intermediate vertex in the shortest path from source to destination. In this step, k is the first vertex.A[i][j]is filled with(A[i][k] + A[k][j]) if (A[i][j] > A[i][k] + A[k][j]).
That is, if the direct distance from the source to the destination is greater than the path through the vertex k, then the cell is filled withA[i][k] + A[k][j].
In this step, k is vertex 1. We calculate the distance from source vertex to destination vertex through this vertex k.
For example: ForA1[2, 4], the direct distance from vertex 2 to 4 is 4 and the sum of the distance from vertex 2 to 4 through vertex (ie. from vertex 2 to 1 and from vertex 1 to 4) is 7. Since4 < 7,A0[2, 4]is filled with 4. - Similarly,
A2is created usingA1. The elements in the second column and the second row are left as they are.
In this step, k is the second vertex (i.e. vertex 2). The remaining steps are the same as in step 2. - Similarly,
A3andA4is also created. A4gives the shortest path between each pair of vertices.
Floyd-Warshall Algorithm
n = no of vertices
A = matrix of dimension n*n
for k = 1 to n
for i = 1 to n
for j = 1 to n
Ak[i, j] = min (Ak-1[i, j], Ak-1[i, k] + Ak-1[k, j])
return ACode
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
namespace FloydWarshallAlgorithm
{
class FloydWarshallAlgo
{
public const int cst = 9999;
static void Main(string[] args)
{
int[,] graph = {
{ 0, 6, cst, 11 },
{ cst, 0, 4, cst },
{ cst, cst, 0, 2 },
{ cst, cst, cst, 0 }
};
FloydWarshall(graph, 4);
}
private static void Print(int[,] distance, int verticesCount)
{
Console.WriteLine("Shortest distances between every pair of vertices:");
for (int i = 0; i < verticesCount; ++i)
{
for (int j = 0; j < verticesCount; ++j)
{
if (distance[i, j] == cst)
Console.Write("cst".PadLeft(7));
else
Console.Write(distance[i, j].ToString().PadLeft(7));
}
Console.WriteLine();
}
}
public static void FloydWarshall(int[,] graph, int verticesCount)
{
int[,] distance = new int[verticesCount, verticesCount];
for (int i = 0; i < verticesCount; ++i)
for (int j = 0; j < verticesCount; ++j)
distance[i, j] = graph[i, j];
for (int k = 0; k < verticesCount; ++k)
{
for (int i = 0; i < verticesCount; ++i)
{
for (int j = 0; j < verticesCount; ++j)
{
if (distance[i, k] + distance[k, j] < distance[i, j])
distance[i, j] = distance[i, k] + distance[k, j];
}
}
}
Print(distance, verticesCount);
}
}
}
Output
Shortest distances between every pair of vertices:
0 6 10 11
cst 0 4 6
cst cst 0 2
cst cst cst 0
0 6 10 11
cst 0 4 6
cst cst 0 2
cst cst cst 0
EmoticonEmoticon