Skip to content

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'\) which will be the output

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

1
2
3
4
5
6
7
8
9
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

1
2
3
4
5
6
7
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

1
2
3
4
5
6
7
8
9
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
\(\Theta(V^4)\) Slow-APSP
\(\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\),

\(\vdots\)

\(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}}\)