Floyd-Warshall

Summarized notes from Introduction to Algorithms, Chapter 25

• graph may include negative weights, no negative-weight cycles
• considers intermediate vertices of path \(p\)
  • intermediate is any vertex other than \(v_1\) or \(v_l\): \(\{v_2, v_3,...v_{l-1}\}\)
  • if \(k\) is not an intermediate vertex pf \(p\), then all intermediate vertices are in set \(\{1,2,...,k-1\}\)
  • if \(k\) is an intermediate vertex, then decompose p:

\(d^{k}_{i,j}\) is weight of shortest path from vertex \(i\) to \(j\) for which all intermediate vertices are in the set \(\{1,2,...,k-1\}\), defined recursively by:

\[\begin{equation} d^{(k)}_{i,j} = \begin{cases} w_{ij} & \text{if } k = 0,\\ min(d^{(k-1)}_{i,j}, d^{(k-1)}_{i,k} + d^{(k-1)}_{k,j}) & \text{if } k \geq 1. \end{cases} \end{equation}\]

• compute \(d^{k}_{i,j}\) in order of increasing values of \(k\)
• input is \(n \times n\) matrix
• output is \(D^{(n)}\) matrix of shortest path weights

Implementation

FLOYD-WARSHALL(W)
    n = W.rows
    D^0 = W
    for k = 1 to n
        let D^k = (d_ij^k) be a new n x n matrix
        for i = 1 to n
            for j = 1 to n
                d_ij^k = min(d_ij^(k-1), d_ik^(k-1) + d_kj^(k-1))
    return D^n

Complexity

Running Time
\(\Theta(V^3)\)	Floyd-Warshall

Constructing shortest path

• One strategy: compute \(D\) then construct predecessor matrix \(\prod\) from \(D\)
• Another strategy: compute during Floyd-Warshall while constructing \(D\)

Transitive closure

• Determines if path from \(i\) to \(j\) exists
• Transitive closure of \(G\) is \(G^* = (V, E^*)\) where \(E^* = \{(i, j)\) : there is a path from \(i\) to \(j\) in \(G\) \(\}\)
• Compute in \(\Theta(V^3)\) time: assign weight 1 to each edge and run Floyd-Warshall → when path exists \(d_{i,j} < \infty\)
• Another strategy that can be faster and more space efficient:
  • substitute logical-OR and logical-AND for operations min and +

when \(k = 0\)

\[\begin{equation} t_{ij}^{(0)} = \begin{cases} 0 & \text{if } i \neq j \text{ and } (i,j) \notin E, \\ 1 & \text{if } i = j \text{ or } (i, j) \in E \end{cases} \end{equation}\]

and for \(k \geq 1\),

\[\begin{equation} {t_{ij}^{(0)} = t_{ij}^{(k-1)} \lor \left( t_{ik}^{(k-1)} \land t_{kj}^{(k-1)}\right)} \end{equation}\]

Implementation

TRANSITIVE-CLOSURE(G)
    n = |G.V|
    let T^0 = t_ij^(0) be a new n x n matrix
    for i = 1 to n
        for j = 1 to n
            if i == j or (i,j) in G.E
                t_ij^(0) = 1
            else
                t_ij^(0) = 0
    for k = 1 to n
        let T^k = t_ij^(k) be a new n x n matrix
        for i = 1 to n
            for j = 1 to n
                t_ij^(k) = t_ij^(k-1) or (t_ik^(k-1) and t_kj^(k-1))
    return T^n

Complexity

Running Time
\(\Theta(V^3)\)	Transitive closure