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_{i,j}^k$ 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:

$$d_{i,j}^{(k)}=\{\begin{array}{ll}{w}_{ij}& \text{if }k=0,\\ min(d_{i,j}^{(k-1)},d_{i,k}^{(k-1)}+d_{k,j}^{(k-1)})& \text{if }k\ge 1.\end{array}$$

• compute $d_{i,j}^k$ 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
$\mathrm{\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^{\ast }=(V,E^{\ast })$ where $E^{\ast }=\{(i,j)$ : there is a path from $i$ to $j$ in $G$ $\}$
• Compute in $\mathrm{\Theta }(V^3)$ time: assign weight 1 to each edge and run Floyd-Warshall → when path exists $d_{i,j}<\mathrm{\infty }$
• Another strategy that can be faster and more space efficient:
  • substitute logical-OR and logical-AND for operations min and +

when $k=0$

$$t_{ij}^{(0)}=\{\begin{array}{ll}0& \text{if }i\ne j\text{ and }(i,j)\notin E,\\ 1& \text{if }i=j\text{ or }(i,j)\in E\end{array}$$

and for $k\ge 1$,

$$t_{ij}^{(0)}=t_{ij}^{(k-1)}\vee (t_{ik}^{(k-1)}\wedge t_{kj}^{(k-1)})$$

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
$\mathrm{\Theta }(V^3)$	Transitive closure