Finding the shortest path in a weighted graph is a difficult task, but finding shortest path from every vertex to every other vertex is a daunting task.

In this post we are going to discuss an algorithm, Floyd-Warshall Algorithm, which is perfectly suited for this job.


Note : In all the pseudo codes, 0-based indexing is used and the indentations are used to differentiate between block of codes.


Problem Statement

Let G be a weighted directed graph with positive and negative weights (but no negative cycles) and V be the set of all vertices. Find the length of the shortest weighted path in G between every pair of vertices in V.

Naive Approach

The easiest approach to find length of shortest path between every pair of vertex in the graph is to traverse every possible path between every pair of vertices. In this approach, we are going to use the property that every part of an optimal path is itself optimal.

Pseudo Code :

minDistance[|V|][|V|]={inf}

findShortestPath(curr, dest)
    if curr==dest
    	return minDistance[curr][curr]=0
    if visited[curr]==true
        return minDistance[curr][dest]
    visited[curr]=true
    sumOfWeights=minDistance[curr][dest]
    for vertex in graph[curr]
        ctr=graph[curr][vertex]+findShortestPath(vertex, dest)
        if ctr<sumOfWeights
            sumOfWeights=ctr
    return minDistance[curr][dest]=sumOfWeights
    
naive_approach()
    for start=0 upto |V|
        for dest=0 upto |V|
            visited[|V|]={false}
            foo=findShortestPath(start, dest)

Time Complexity : O(|V|2*( |V|+|E| ))

Space Complexity : O(|V|2)


Floyd-Warshall Algorithm

The Floyd-Warshall algorithm is an example of dynamic programming, published independently by Robert Floyd and Stephen Warshall in 1962.

Like the Bellman-Ford algorithm and Dijkstra's algorithm, it computes the shortest weighted path in a graph. However unlike Bellman-Ford algorithm and Dijkstra's algorithm, which finds shortest path from a single source, Floyd-Warshall algorithm finds the shortest path from every vertex in the graph.

The algorithm compares all possible paths between each pair of vertices in the graph. It does so by improving on the estimate of the shortest path until the estimate is optimal. The algorithm basically checks whether a vertex k is or is not in the shortest path between vertices i and j.

Recursion

Let us define the shortestPath(i,j,k) to be the length of the shortest path between vertex i and vertex j using only vertices from the set {1,2,3,...,k-1,k} as intermediate points. Our goal is to find the length of the shortest path between every vertices i and j in V using the vertices from V as intermediate points.

For each pair of vertices i and j :

  • The shortest path passes through k i.e. the path goes from i to k and then from k to j.
  • The shortest path does not passes through k.

Hence the recursive formula is as follows,

Base Case :
shortestPath(i,j,0)=graph(i,j)
Recursive Case :
shortestPath(i,j,k)=min(shortestPath(i,j,k-1), shortestPath(i,k,k-1)+shortestPath(k,j,k-1))

The algorithm takes advantage of the dynamic programming nature of the problem to efficiently do this recursion.

Pseudo Code :

floydWarshall(graph, V, E)
    minDistance[|V|][|V|]={inf}

    // Initialising minDistance as the graph
    for edge=0 upto |E|
        u=edge.first
        v=edge.second
        minDistance[u][v]=graph[u][v]
    
    // Initialising minDistance for each vertex
    for vertex=0 upto |V|
        minDistance[vertex][vertex]=0
    
    for mid=0 upto |V|
        for start=0 upto |V|
            for dest=0 upto |V|
                if minDistance[start][dest]>minDistance[start][mid]+minDistance[mid][dest]
                    minDistance[start][dest]=minDistance[start][mid]+minDistance[mid][dest]
    return minDistance                    

Time Complexity : O(|V|3)

Space Complexity : O(|V|2)

Running Floyd-Warshall Algorithm on a Directed Tree
Running Floyd-Warshall Algorithm on a Directed Tree

Issue with Negative Cycle

A negative cycle is a cycle whose sum of edges in the cycle is negative. The vertices in a negative cycle can never have a shortest path because we can always retraverse the negative cycle which will reduce the sum of weights and hence giving us an infinite loop.

However Floyd-Warshall algorithm can be used to detect negative cycles. The intuition behind this is that the minDistance[v][v]=0 for any vertex v, but if there exists a negative cycle, taking the path [v,....,C,....,v] will only reduce the shortest path (where C is a negative cycle). Hence if a negative cycle exists in the graph then there will be atleast one negative diagonal element in minDistance.

Applications

  • Computing similarity between graphs.
  • Finding transitive closure of a weighted graph.
  • Testing whether an undirected graph is bipartite.
  • Detecting whether a graph contains a negative cycle.
  • For finding Optimal Routing between vertices.

Till date, Floyd-Warshall algorithm is the most efficient algorithm suitable for this job. However you never what is in store for us in the future.