Floyd Warshall Algorithm

Description: As per wiki, in computer science, the Floyd–Warshall algorithm (also known as Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm, or the WFI algorithm) is an algorithm for finding shortest paths in a directed weighted graph with positive or negative edge weights (but with no negative cycles). A single execution of the algorithm will find the lengths (summed weights) of shortest paths between all pairs of vertices. 

Although it does not return details of the paths themselves, it is possible to reconstruct the paths with simple modifications to the algorithm. 

Algorithm: Given a graph Graph[][] with nodes 1...N, we need to evaluate the matrix say shortestPathMatrix[][] where shortestPathMatrix[ni][nj] tells the shortest path between nodes ni and nj.

The algorithm uses dynamic programming to evaluate the above matrix. It relies on a obvious thing that the shortest path between n1 and n2 will have a intermediate node say nk:

 

That means, we can say for every intermediate node k:

shortestPathMatrix[i][j] = MIN (shortestPathMatrix[i][k] + shortestPathMatrix[k][j], shortestPathMatrix[i][j]

So the steps are now simple:

• Initialize shortestPathMatrix to Graph.
• FOR k = 0 TO n:
• FOR i = 0 TO n:
• FOR j = 0 TO n:
• shortestPathMatrix[i][j] = MIN (shortestPathMatrix[i][k] + shortestPathMatrix[k][j], shortestPathMatrix[i][j])

 

That's all!

Implementation in C#:

class Graph

{

    public Graph(int[,] adjMat)

    {

        this.adjacencyMatrix = adjMat;

    }

    

    public int[,] FloydWarshall()

    {

        int n = this.adjacencyMatrix?.GetLength(0) ?? 0;

        if (n == 0)

        {

            return null;

        }

        int[,] dist = this.InitDistance();

        

        for (int k = 0; k < n; ++k)

        {

            for (int i = 0; i < n; ++i)

            {

                for (int j = 0; j < n; ++j)

                {

                    if (dist[i, k] + dist[k, j] < dist[i, j])

                    {

                        dist[i, j] = dist[i, k] + dist[k, j];

                    }

                }

            }

        }

        return dist;

    }

    

    private int[,] InitDistance()

    {

        int n = this.adjacencyMatrix.GetLength(0);

        int[,] dist = new int[n, n];

        Console.WriteLine(n);

        for (int i = 0; i < n; ++i)

        {

            for (int j = 0; j < n; ++j)

            {

                dist[i, j] = this.adjacencyMatrix[i, j] >= 0 ?

                             this.adjacencyMatrix[i, j] :

                             Graph.INF;

            }

        }

        return dist;

    }

    

    private int[,] adjacencyMatrix;

    private const int INF = 9999;

}

Complexity: O(n^3)