Matrix Multiplication

Summarized notes from Introduction to Algorithms, Chapter 25

• dynamic programming algorithm for finding all-pairs shortest paths
• looks like repeated matrix multiplication
• compute shortest path by extending shortest path edge by edge
• Start with $L^{(1)}=W$ which represents weights from original graph
• after $n-1$ repetitions will converge if no cycles

• Solution computes matrix $L^{\prime }$ which will be the output

• Extend-shortest-paths method is used to update weight estimate:

EXTENDED-SHORTEST-PATHS(L, W)
    n = L.rows
    let L' = (l'_ij) be a new n x n matrix
    for i = 1 to n
        for j = 1 to n
            l'_ij = ∞
            for k = 1 to n
                l'_ij = min(l'_ij, l_ik + w_kj)
    return L'

Two versions

Slow All-Pairs

SLOW-ALL-PAIRS-SHORTEST-PATHS(W)
    n = W.rows
    L^1 = W
    for m = 2 to n-1
        let L^m be a new n x n matrix
        L^m = EXTENDED-SHORTEST-PATHS(L^(m-1), W)
    return L^(m-1)

Faster All-Pairs

FASTER-ALL-PAIRS-SHORTEST-PATHS(W)
    n = W.rows
    L^1 = W
    m = 1
    while m < n-1
        let L^(2m) be a new n x n matrix
        L^(2m) = EXTENDED-SHORTEST-PATHS(L^(m), L^(m))
        m = 2m
    return L^(m)

Complexity

Running Time
$\mathrm{\Theta }(V^4)$	Slow-APSP
$\mathrm{\Theta }(V^3\lg V)$	Faster-APSP

Why is Faster-APSP faster?
=> no need to compute all $L^{(m)}$ matrices → iterate fewer times using repeated squaring

$L^{(1)}=W$,

$L^{(2)}=W^2=W\cdot W$,

$L^{(4)}=W^4=W^2\cdot W^2$,

$L^{(8)}=W^8=W^4\cdot W^4$,

$⋮$

$L^{(2^{\lceil \lg (n-1)\rceil )}}=W^{2^{\lceil \lg (n-1)\rceil }}=W^{2^{\lceil \lg (n-1)\rceil -1}}\cdot W^{2^{\lceil \lg (n-1)\rceil -1}}$