Skip to content

25.1 Shortest paths and matrix multiplication

25.1-1

Run $\text{SLOW-ALL-PAIRS-SHORTEST-PATHS}$ on the weighted, directed graph of Figure 25.2, showing the matrices that result for each iteration of the loop. Then do the same for $\text{FASTER-ALL-PAIRS-SHORTEST-PATHS}$.

  • Initial:

    $$ \begin{pmatrix} 0 & \infty & \infty & \infty & -1 & \infty \\ 1 & 0 & \infty & 2 & \infty & \infty \\ \infty & 2 & 0 & \infty & \infty & -8 \\ -4 & \infty & \infty & 0 & 3 & \infty \\ \infty & 7 & \infty & \infty & 0 & \infty \\ \infty & 5 & 10 & \infty & \infty & 0 \end{pmatrix} $$

  • Slow:

    $m = 2$:

    $$ \begin{pmatrix} 0 & 6 & \infty & \infty & -1 & \infty \\ -2 & 0 & \infty & 2 & 0 & \infty \\ 3 & -3 & 0 & 4 & \infty & -8 \\ -4 & 10 & \infty & 0 & -5 & \infty \\ 8 & 7 & \infty & 9 & 0 & \infty \\ 6 & 5 & 10 & 7 & \infty & 0 \end{pmatrix} $$

    $m = 3$:

    $$ \begin{pmatrix} 0 & 6 & \infty & 8 & -1 & \infty \\ -2 & 0 & \infty & 2 & -3 & \infty \\ -2 & -3 & 0 & -1 & 2 & -8 \\ -4 & 2 & \infty & 0 & -5 & \infty \\ 5 & 7 & \infty & 9 & 0 & \infty \\ 3 & 5 & 10 & 7 & 5 & 0 \end{pmatrix} $$

    $m = 4$:

    $$ \begin{pmatrix} 0 & 6 & \infty & 8 & -1 & \infty \\ -2 & 0 & \infty & 2 & -3 & \infty \\ -5 & -3 & 0 & -1 & -3 & -8 \\ -4 & 2 & \infty & 0 & -5 & \infty \\ 5 & 7 & \infty & 9 & 0 & \infty \\ 3 & 5 & 10 & 7 & 2 & 0 \end{pmatrix} $$

    $m = 5$:

    $$ \begin{pmatrix} 0 & 6 & \infty & 8 & -1 & \infty \\ -2 & 0 & \infty & 2 & -3 & \infty \\ -5 & -3 & 0 & -1 & -6 & -8 \\ -4 & 2 & \infty & 0 & -5 & \infty \\ 5 & 7 & \infty & 9 & 0 & \infty \\ 3 & 5 & 10 & 7 & 2 & 0 \end{pmatrix} $$

  • Fast:

    $m = 2$:

    $$ \begin{pmatrix} 0 & 6 & \infty & \infty & -1 & \infty \\ -2 & 0 & \infty & 2 & 0 & \infty \\ 3 & -3 & 0 & 4 & \infty & -8 \\ -4 & 10 & \infty & 0 & -5 & \infty \\ 8 & 7 & \infty & 9 & 0 & \infty \\ 6 & 5 & 10 & 7 & \infty & 0 \end{pmatrix} $$

    $m = 4$:

    $$ \begin{pmatrix} 0 & 6 & \infty & 8 & -1 & \infty \\ -2 & 0 & \infty & 2 & -3 & \infty \\ -5 & -3 & 0 & -1 & -3 & -8 \\ -4 & 2 & \infty & 0 & -5 & \infty \\ 5 & 7 & \infty & 9 & 0 & \infty \\ 3 & 5 & 10 & 7 & 2 & 0 \end{pmatrix} $$

    $m = 8$:

    $$ \begin{pmatrix} 0 & 6 & \infty & 8 & -1 & \infty \\ -2 & 0 & \infty & 2 & -3 & \infty \\ -5 & -3 & 0 & -1 & -6 & -8 \\ -4 & 2 & \infty & 0 & -5 & \infty \\ 5 & 7 & \infty & 9 & 0 & \infty \\ 3 & 5 & 10 & 7 & 2 & 0 \end{pmatrix} $$

25.1-2

Why do we require that $w_{ii} = 0$ for all $1 \le i \le n$?

This is consistent with the fact that the shortest path from a vertex to itself is the empty path of weight $0$. If there were another path of weight less than $0$ then it must be a negative-weight cycle, since it starts and ends at $v_i$.

If $w_{ii} \ne 0$, then $L^{(1)}$ produced after the first run of $\text{EXTEND-SHORTEST-PATHS}$ would not contain the minimum weight of any path from $i$ to its neighbours. If $w_{ii} = 0$, then in line 7 of $\text{EXTEND-SHORTEST-PATHS}$, the second argument to $min$ would not equal the weight of the edge going from $i$ to its neighbours.

25.1-3

What does the matrix

$$ L^{(0)} = \begin{pmatrix} 0 & \infty & \infty & \cdots & \infty \\ \infty & 0 & \infty & \cdots & \infty \\ \infty & \infty & 0 & \cdots & \infty \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \infty & \infty & \infty & \cdots & 0 \end{pmatrix} $$

used in the shortest-paths algorithms correspond to in regular matrix multiplication?

The identity matrix.

25.1-4

Show that matrix multiplication defined by $\text{EXTEND-SHORTEST-PATHS}$ is associative.

To verify associativity, we need to check that $(W^iW^j)W^p = W^i(W^jW^p)$ for all $i$, $j$ and $p$, where we use the matrix multiplication defined by the $\text{EXTEND-SHORTEST-PATHS}$ procedure. Consider entry $(a, b)$ of the left hand side. This is:

$$ \begin{aligned} \min_{1 \le k \le n} [W^iW^j]_{a, k} + W_{k, b}^p & = \min_{1 \le k \le n} \min_{1 \le q \le n} W_{a, q}^i + W_{q, k}^j + W_{k, b}^p \\ & = \min_{1 \le q \le n} W_{a, q}^i + \min_{1 \le k \le n} W_{q, k}^j + W_{k, b}^p \\ & = \min_{1 \le q \le n} W_{a, q}^i + [W^jW^p]_{q, b}, \end{aligned} $$

which is precisely entry $(a, b)$ of the right hand side.

25.1-5

Show how to express the single-source shortest-paths problem as a product of matrices and a vector. Describe how evaluating this product corresponds to a Bellman-Ford-like algorithm (see Section 24.1).

(Removed)

25.1-6

Suppose we also wish to compute the vertices on shortest paths in the algorithms of this section. Show how to compute the predecessor matrix $\prod$ from the completed matrix $L$ of shortest-path weights in $O(n^3)$ time.

For each source vertex $v_i$ we need to compute the shortest-paths tree for $v_i$. To do this, we need to compute the predecessor for each $j \ne i$. For fixed $i$ and $j$, this is the value of $k$ such that $L_{i, k} + w(k, j) = L[i, j]$. Since there are $n$ vertices whose trees need computing, $n$ vertices for each such tree whose predecessors need computing, and it takes $O(n)$ to compute this for each one (checking each possible $k$), the total time is $O(n^3)$.

25.1-7

We can also compute the vertices on shortest paths as we compute the shortestpath weights. Define $\pi_{ij}^{(m)}$ as the predecessor of vertex $j$ on any minimum-weight path from $i$ to $j$ that contains at most $m$ edges. Modify the $\text{EXTEND-SHORTESTPATHS}$ and $\text{SLOW-ALL-PAIRS-SHORTEST-PATHS}$ procedures to compute the matrices$\prod^{(1)}, \prod^{(2)}, \ldots, \prod^{(n - 1)}$ as the matrices $L^{(1)}, L^{(2)}, \ldots, L^{(n - 1)}$ are computed.

To have the procedure compute the predecessor along the shortest path, see the modified procedures, $\text{EXTEND-SHORTEST-PATH-MOD}$ and $\text{SLOW-ALL-PAIRS-SHORTEST-PATHS-MOD}$

EXTEND-SHORTEST-PATH-MOD(∏, L, W)
    n = L.row
    let L' = l'[i, j] be a new n × n matirx
    ∏' = π'[i, j] is a new n × n matrix
    for i = 1 to n
        for j = 1 to n
            l'[i, j] = ∞
            π'[i, j] = NIL
            for k = 1 to n
                if l[i, k] + l[k, j] < l[i, j]
                    l[i, j] = l[i, k] + l[k, j]
                    if k != j
                        π'[i, j] = k
                    else
                        π'[i, j] = π[i, j]
    return (∏', L')

SLOW-ALL-PAIRS-SHORTEST-PATHS-MOD(W)
    n = W.rows
    L(1) = W
    ∏(1) = π[i, j](1) where π[i, j](1) = i if there is an edge from i to j, and NIL otherwise
    for m = 2 to n - 1
        ∏(m), L(m) = EXTEND-SHORTEST-PATH-MOD(∏(m - 1), L(m - 1), W)
    return (∏(n - 1), L(n - 1))

25.1-8

The $\text{FASTER-ALL-PAIRS-SHORTEST-PATHS}$ procedure, as written, requires us to store $\lceil \lg(n - 1) \rceil$ matrices, each with $n^2$ elements, for a total space requirement of $\Theta(n^2\lg n)$. Modify the procedure to require only $\Theta(n^2)$ space by using only two $n \times n$ matrices.

We can overwrite matrices as we go. Let $A \star B$ denote multiplication defined by the $\text{EXTEND-SHORTEST-PATHS}$ procedure. Then we modify $\text{FASTER-ALL-EXTEND-SHORTEST-PATHS}(W)$. We initially create an $n$ by $n$ matrix $L$. Delete line 5 of the algorithm, and change line 6 to $L = W \star W$, followed by $W = L$.

25.1-9

Modify $\text{FASTER-ALL-PAIRS-SHORTEST-PATHS}$ so that it can determine whether the graph contains a negative-weight cycle.

For the modification, keep computing for one step more than the original, that is, we compute all the way up to $L^{(2k + 1)}$ where $2^k > n - 1$. Then, if there aren't any negative weight cycles, then, we will have that the two matrices should be equal since having no negative weight cycles means that between any two vertices, there is a path that is tied for shortest and contains at most $n - 1$ edges.

However, if there is a cycle of negative total weight, we know that it's length is at most $n$, so, since we are allowing paths to be larger by $2k \ge n$ between these two matrices, we have that we would need to have all of the vertices on the cycle have their distance reduce by at least the negative weight of the cycle. Since we can detect exactly when there is a negative cycle, based on when these two matrices are different. This algorithm works. It also only takes time equal to a single matrix multiplication which is littlee oh of the unmodified algorithm.

25.1-10

Give an efficient algorithm to find the length (number of edges) of a minimum-length negative-weight cycle in a graph.

(Removed)