Floyd-Warshall is designed to solve the all pairs shortest path problem. This is the SSSP solved n times. Using Bellman-Ford, this would take \(O(n^4)\) time on sparse graphs. Thus, we need a more efficient approach.

Outline

• Input: A weighted directed graph with (n) vertices.
• Goal: Compute shortest paths between all pairs of vertices.
• Key idea: We create subproblems by limiting the number of vertices we are allowed to look at. This allows us to do the processing of each sub-problem in constant time.

Defining subproblems

Define \(D^{(k)}[i][j]\): the shortest path distance from vertex (i) to vertex (j) using only intermediate vertices from the set \({1, 2, \dots, k}\).

Base case

\(D^{(0)}[i][j] = w(i, j)\) where \(w(i, j)\) is the direct edge weight (or \(\infty\) if no edge exists).

Recursive Step

\(D^{(k)}[i][j]= \min (D^{(k-1)}[i][j], D^{(k-1)}[i][k] + D^{(k-1)}[i][k])\)

Here is how this may be implemented:

procedure FloydWarshall(Graph):
    // Let Graph be represented as adjacency matrix dist[][]
    // dist[i][j] = weight of edge (i, j), or ∞ if no edge

    n = number of vertices in Graph

    // Initialize distance matrix (Handle Base Cases)
    for i from 1 to n:
        for j from 1 to n:
            if i == j:
                dist[i][j] = 0
            else if edge(i, j) exists:
                dist[i][j] = weight(i, j)
            else:
                dist[i][j] = ∞

    // Main triple loop (Recursive Steps)
    for k from 1 to n:                // intermediate vertex
        for i from 1 to n:            // source vertex
            for j from 1 to n:        // destination vertex
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

Complexity

• Time: \(O(n^3)\) (triple nested loop over \(k, i, j\)).

  Reasoning in a different way, there are \(O(n^3)\) states and each state takes \(O(1)\) time to compute.

• Space: \(O(n^2)\) (distance matrix).

Whether it is possible to come up with an algorithm for the all pairs shortest path problem that works in less than \(O(n^3)\) time is an open problem.

Example Problems

All-pairs reachability problem

Given a directed graph, return a matrix M such that M [u][v] = 1 if u can reach v, 0 otherwise. Floyd-Warshall leads to the classic \(O(V^3)\) approach, where you repeatedly update reachability using an intermediate-vertex recurrence. It is easy to implement and works well for dense graphs conceptually, but it is cubic time.

However, there is a faster approach to this problem using matrices.

Diameter

The diameter of the graph is defined as follows:

The diameter of a graph (sometimes called the width) is the number of edges/total weight on the longest path between two nodes in the graph.

There are multiple ways to approach this problem.

For a general graph, the diameter of a graph can be computed by using a shortest path algorithm to compute shortest paths between all pairs of vertices, and then taking the maximum of the distances that it computes.

For a general, weighted graph with arbitrary positive or negative weights, the best choice is Floyd-Warshall in \(O(V^3)\) time. However, in the following circuimstances, simplications can be made:

• In a graph with positive edge weights, repeatedly use Dijkstra's algorithm , once for each possible starting vertex. In a graph with \(n\) vertices and \(m\) edges, this takes time \(O(mn+n^2 \log⁡n)\).
• In an unweighted-graph, Dijkstra's algorithm may be replaced by a breadth-first search, giving time \(O(nm)\)
• In an undirected tree, we first perform a DFS (or BFS) from any node to find the farthest node, which becomes one endpoint of the longest path. Then, starting from this farthest node, we perform another DFS to find the node farthest from it.

  Refer to Graph Diameter Calculation for the algorithm.

Alternatively, the diameter may be computed using an algorithm based on fast matrix multiplication, in time proportional to the time for multiplying \(n \times n\) matrices (approximately \(O(n^{2.37})\)).