22. Single-Source Shortest Paths

Exercises

22.1-1

Use the VisuAlgo tool to see the Bellman-Ford algorithm in action on the graph of Figure 22.4. Choose the option Input Graph using 0-indexing of vertices and the edge list format (click the Help! button for further details or see Exercise 22.1-5). Enter the following content and press Submit:

5 10
0 1 5
0 2 8
0 3 -4
1 0 -2
2 1 -3
2 3 9
3 1 7
3 4 2
4 0 6
4 2 7

The vertices are mapped as follows: $s \to 4, t \to 0, y \to 2, x \to 1, z \to 3$ to force the tool to relax the edges in the same order as in the book.

The tool shows you the graph in some layout. Press the Help button for instructions how to manually rearrange the vertices to recreate Figure 22.4. Once ready, press the Done button. After selecting the Bellman-Ford algorithm, you can specify its variant and the source vertex. Press the play button to watch how edges are relaxed.

At the time of this writing, the tool becomes unresponsive when there are negative-weight cycles reachable from the source. This happens in the second part of this exercise, so the answer should be FALSE.

22.1-2

Available in the latest revision of the IM.

22.1-3

Available in the latest revision of the IM.

22.1-4

Available in the latest revision of the IM.

22.1-5

Available in the latest revision of the IM.

22.1-6

Available in the latest revision of the IM.

22.1-7

Available in the latest revision of the IM.

22.2-1

Use the VisuAlgo tool as in Exercise 22.1-1 and enter the following graph of Figure 22.5:

6 10
0 1 5
0 2 3
1 2 2
1 3 6
2 3 7
2 4 4
2 5 2
3 4 -1
3 5 1
4 5 -2

Observe that after one iteration of Bellman-Ford all vertices are set to their final values. This emulates finding shortest paths in a dag. The vertices are mapped in topological order (for example, $r \to 0, s\to 1, \dots$).

22.2-2

Available in the latest revision of the IM.

22.2-3 🌟

Shows two ways to transform a PERT chart with weights on vertices to a PERT chart with weights on edges. This allows running the original code on a new graph.

Available in the latest revision of the IM.

★ 22.2-4

Available in the latest revision of the IM.

22.3-1

Use the VisuAlgo tool as in Exercise 22.1-1 and Exercise 22.2-1 and select Dijsktra's original version of the algorithm. Also, reuse the examples from the previously mentioned exercises to set up the matching edge list.

22.3-2

Available in the latest revision of the IM.

22.3-3

Available in the latest revision of the IM.

22.3-4

Available in the latest revision of the IM.

22.3-5

Available in the latest revision of the IM.

22.3-6

Available in the latest revision of the IM.

22.3-7

Available in the latest revision of the IM.

22.3-8

The following citation from the book is the essence of the solution:

You can think of Dijkstra’s algorithm as generalizing breadth-first search to weighted graphs. A wave emanates from the source, and the first time that a wave arrives at a vertex, a new wave emanates from that vertex. Whereas breadth-first search operates as if each wave takes unit time to traverse an edge, in a weighted graph, the time for a wave to traverse an edge is given by the edge’s weight.

As given in the exercise, we can assume that no two vertices have the same shortest-path weights from source vertex $s$. This allows us to emulate the weights with distances by inserting extra vertices comprising the set $V'$. For example, the edge $e=(u,v) \in E$ would be transformed into a series of edges and vertices in $G'$: $(u,uv_1),(uv_1,uv_2),\dots,(uv_k,v)$, where $k=w(e)-1$. If $k=0$, just leave the original edge. Therefore,

$$\vert{}V'\vert{} = \sum_{e \in E} (w(e) - 1) = \sum_{e \in E} w(e) - \vert{}E\vert{}.$$

By construction, the unweighted shortest-path distance in the new graph, let's call it $\delta'(s, v)$, is exactly equal to the weighted shortest-path distance $\delta(s, v)$ in the original graph for all $v \in V$. BFS always discovers and colors vertices black in monotonically increasing order of their unweighted distance from the source. Dijkstra's algorithm always extracts vertices from its priority queue in monotonically increasing order of their weighted distance from the source. Because all distances are unique, there are no ties for either algorithm to break arbitrarily. Since both algorithms process the vertices in the same order based on the exact same distance values, the order must be identical.

22.3-9 🌟

When keys are known to be integers in the range 0 to $k$ and the key values extracted are monotonically increasing over time, we can implement a min-priority queue so that any sequence of $m$ INSERT, EXTRACT-MIN, and DECREASE-KEY operations takes $O(m+k)$ time. This exercise shows how this proprietary priority queue can reduce the time of Dijkstra’s algorithm.

Available in the latest revision of the IM.

22.3-10

Available in the latest revision of the IM.

22.3-11 🌟

Highlights an important special case, where Dijkstra's algorithm still works even though edges that leave the source vertex $s$ may have negative weights.

Available in the latest revision of the IM.

22.3-12

Available in the latest revision of the IM.

22.4-1

The constraint graph representing the given system of difference constraints.

By running the Bellman-Ford algorithm from the super-source vertex $v_0$, we find that there are no negative-weight cycles, which means a feasible solution exists. The resulting shortest-path weights provide the solution for each variable $x_i$, which are displayed inside their respective vertices.

22.4-2

The constraint graph representing the given system of difference constraints.

The graph contains a negative-weight cycle $v_4 \to v_2 \to v_3 \to v_5 \to v_1 \to v_4$, so no feasible solution exists.

22.4-3

Available in the latest revision of the IM.

22.4-4 🌟

Expresses the single-pair shortest-path problem as a linear program.

Available in the latest revision of the IM.

22.4-5

Available in the latest revision of the IM.

22.4-6

Available in the latest revision of the IM.

22.4-7

Available in the latest revision of the IM.

★ 22.4-8

The trick to solving this exercise is realizing that Bellman-Ford doesn't just maximize the sum $\sum_{i=1}^n x_i$—it actually maximizes each individual variable $x_i$ simultaneously! You may also want to take a look at Exercise 24.4-4.

Let the solution produced by the Bellman-Ford algorithm be $x = (x_1, x_2, \dots, x_n)$, where each $x_i = \delta(v_0, v_i)$. By the definition of the constraint graph, there is a directed edge from $v_0$ to every other vertex $v_i$ with a weight of exactly 0. Therefore, the shortest path from $v_0$ to $v_i$ can never be greater than 0. This guarantees $x_i \le 0$ for all $x_i$.

Suppose there is some other arbitrary feasible solution $y = (y_1, y_2, \dots, y_n)$ that satisfies both the system $Ay \le b$ and the condition $y_i \le 0$ for all $y_i$. We want to see how $y_i$ compares to our Bellman-Ford solution $x_i$.

Pick any vertex $v_i$. In the constraint graph, consider the shortest path from $v_0$ to $v_i$ that Bellman-Ford found. Let's say this path goes through a sequence of vertices:

$$v_0 \to v_{k_1} \to v_{k_2} \to \dots \to v_{k_m} \to v_i.$$

Because $y$ is a valid solution to the system, it must satisfy the difference constraints corresponding to every single edge along this path:

• $y_{k_1} - y_0 \le w(v_0, v_{k_1})$

• $y_{k_2} - y_{k_1} \le w(v_{k_1}, v_{k_2})$

• $\dots$

• $y_i - y_{k_m} \le w(v_{k_m}, v_i)$

If we sum all of these inequalities together, the intermediate variables on the left side completely cancel each other out in a telescoping sum. We are left with:

$$y_i - y_0 \le w(v_0, v_{k_1}) + w(v_{k_1}, v_{k_2}) + \dots + w(v_{k_m}, v_i).$$

Since $y_0 = 0$, the left side is just $y_i$. The right side is exactly the total weight of the shortest path from $v_0$ to $v_i$, which is our Bellman-Ford solution $x_i$. Therefore, we have proven that $y_i \le x_i$ for every single variable. Because the Bellman-Ford solution $x_i$ is greater than or equal to any other feasible solution $y_i$ on a component-by-component basis, it mathematically follows that their sums share the same relationship:

$$\sum_{i=1}^n y_i \le \sum_{i=1}^n x_i.$$

Thus, the Bellman-Ford algorithm maximizes the sum.

★ 22.4-9

Let the solution produced by the Bellman-Ford algorithm be $x = (x_1, x_2, \dots, x_n)$, where each $x_i = \delta(v_0, v_i)$. At least one vertex must have a shortest path of exactly 0 (otherwise, all vertices would be part of a negative-weight cycle, which means no feasible solution exists). Therefore, $\max \{x_i\} = 0$, so the spread of the Bellman-Ford solution is

$$(\max \{x_i\} - \min \{x_i\}) = 0 - \min \{x_i\} = -\min \{x_i\}.$$

Suppose there is some other solution $y = (y_1, y_2, \dots, y_n)$ that satisfies the system $Ay \le b$. Let's shift it, so its maximum value is exactly 0. We define a new solution $y'$ where $y'_i = y_i - \max \{y_j\}$ (Lemma 22.8 ensures that $y'$ is also a valid solution), thus $y'_i \le 0$ for all $i$. By the property established in the previous exercise, we have $y'_i \le x_i$ for every single variable. Thus,

$$\min \{y'_i\} \le \min \{x_i\} \iff -\min \{y'_i\} \ge -\min \{x_i\}.$$

Since shifting a solution by a constant doesn't change its spread, the spread of the original arbitrary solution $y$ is larger. Therefore, no feasible solution can have a tighter spread than the Bellman-Ford solution.

Practical Application: Construction Scheduling

The quantity $(\max \{x_i\} - \min \{x_i\})$ represents the time elapsed between the start of the very first job and the start of the very last job. This is effectively the overall duration of the active project. By minimizing this spread, the Bellman-Ford algorithm produces a highly compressed schedule.

22.4-10 🌟

Shows how to adapt the Bellman-Ford algorithm to solve a constraint system with single-variable inequalities.

Available in the latest revision of the IM.

22.4-11

Available in the latest revision of the IM.

★ 22.4-12

We can solve this by running Bellman-Ford on the constraint graph with a slightly modified relaxation step, using the idea from the previous exercise.

For $i = 1$ to $\vert{}V\vert{} - 1$, iterate over every edge $(u, v) \in E$ with weight $w$:

• If $v$ is constrained to be an integer: $x_v = \min(x_v, \lfloor x_u + w \rfloor)$

• If $v$ is allowed to be real-valued: $x_v = \min(x_v, x_u + w)$

We also need a way to specify the list of variables in the model that should be integers. The total asymptotic running time of this altered algorithm is the same as the original version.

22.5-1

In Figure 22.2 (b) replace edge $(t,x)$ with edge $(y,x)$. In Figure 22.2 (c) do the opposite.

22.5-2

Available in the latest revision of the IM.

22.5-3

Available in the latest revision of the IM.

22.5-4

Available in the latest revision of the IM.

22.5-5

Available in the latest revision of the IM.

22.5-6

Available in the latest revision of the IM.

22.5-7

Available in the latest revision of the IM.

22.5-8

Available in the latest revision of the IM.

Problems

22-1 Yen’s improvement to Bellman-Ford

Available in the latest revision of the IM.

22-2 Nesting boxes

Available in the latest revision of the IM.

22-3 Arbitrage

Available in the latest revision of the IM.

22-4 Gabow’s scaling algorithm for single-source shortest paths

Available in the latest revision of the IM.

22-5 Karp’s minimum mean-weight cycle algorithm

a.

If $G$ contains a negative-weight cycle, then $\mu^*<0$, so $\mu^*=0$ means $G$ contains no negative-weight cycles.

Because $\mu^*=0$, every cycle in the graph has a weight $\ge 0$. If you have a path from $s$ to $v$ that contains a cycle, you can remove that cycle to create a new path. Since the cycle's weight was $\ge 0$, the new path's weight will be less than or equal to the original path. Therefore, for any shortest path from $s$ to $v$, there is always a simple path that achieves that same shortest-path weight $\delta(s,v)$. Furthermore, $\delta(s,v)$ must be the minimum of the shortest paths of length $k \in [0,n-1]$. This perfectly matches the formula $\min \{\delta_k(s, v) : 0 \le k \le n - 1\}$.

b.

The denominator is always positive. The $\delta_n(s,v)$ is either $\infty$ (when there is no path of length $n$ from $s$ to $v$) or some finite value $w(p)$. In the latter case, the path $p$ must contain a simple cycle $c$ of length $l \ge 1$. We also know that $w(c) \ge 0$ (see part(a)). If we remove $c$ from $p$, we are left with a new path, let's call it $p'$, which has exactly $n-l$ edges. The weight of this specific path is $w(p') = \delta_n(s,v) - w(c)$. Thus,

$$\delta_{n-l}(s,v) \le w(p') \implies \delta_n(s,v) \ge \delta_{n-l}(s,v) + w(c) \implies \delta_n(s,v) \ge \delta_{n-l}(s,v).$$

Therefore, for $k=n-l$ the numerator is non-negative, which concludes the proof.

c.

We know that $G$ contains no negative-weight cycles from part (a). Using the hint from the book, we get the following two inequalities by traversing the cycle $c$ from different starting points:

• $\delta(s,u) \le \delta(s,v)-x \implies \delta(s,v) \ge \delta(s,u)+x$

• $\delta(s,v) \le \delta(s,u)+x$

Consequently, we have $\delta(s,v) =\delta(s,u)+x$.

d.

We need to show that there is some vertex $v$ on the cycle, where

$$\delta_n(s, v) \le \delta_k(s, v) \text{ for all } 0 \le k \le n-1 \iff \delta_n(s, v) \le \delta(s, v).$$

Combining this with part (b) shows that the maximum is 0 for some vertex $v$.

Let $c$ be our minimum mean-weight cycle. Since $\mu^* = 0$, $c$ has a total weight of exactly 0.

• Pick any vertex $u$ on the cycle $c$. Because all vertices are reachable from $s$, there exists a shortest path from $s$ to $u$. Let this shortest path have $k$ edges. Because we established in part (a) that shortest paths can be simple, we know $k \le n - 1$. The weight of this path is exactly $\delta(s, u)$.

• Now, follow the hint: extend this path forward by continuing along the edges of the cycle $c$ for exactly $n-k$ more edges. Let $v$ be the vertex you land on after tracing those $n-k$ edges. (Note: Because you are tracing along a cycle, you might loop around it, but you will eventually land on some vertex $v$ that is also on $c$).

• The first part of the path to $v$ has $k$ edges, and the extension has $n-k$ edges. The total length is exactly $n$ edges. The first part has a weight of $\delta(s, u)$. The extension is a walk along a 0-weight cycle. Even if it wraps around the cycle multiple times, those full loops add 0 weight. The net weight added is just the weight of the simple path along the cycle from $u$ to $v$ which we will call $x$.

$$\delta_n(s, v) \le \delta(s, u) + x=\delta(s, v) \text{ by part (c)} \implies \delta_n(s, v) \le \delta(s, v).$$

e.

If you have a set of numbers where every number is $\ge 0$ (part (b)), and at least one of those numbers is exactly 0 (part (d)), the minimum value of that entire set is strictly 0.

f.

If you add a constant $t$ to the weight of each edge of $G$, then $\mu(c)$ increases by $t$ for every cycle. Also, $\min \{\mu(c)+t\}=t+\min \{\mu(c)\}$, which entails that $\mu^*$ also increases by $t$.

Part (e) proved that the formula equals 0, but only under the strict assumption that $\mu^* = 0$. Let $G$ be a graph with a minimum mean-weight cycle of $\mu^*$. We can construct a modified graph $G'$ by subtracting $\mu^*$ from the weight of every edge (which is the same as adding $t=-\mu^*$). By the rule we just proved above, the new minimum mean-weight cycle of $G'$ is precisely $\mu'^* = \mu^* - \mu^* = 0$. Hence, we can safely apply the theorem from part (e) to this new graph. Let $\delta'_k(s, v)$ be the shortest path of exactly $k$ edges in $G'$:

$$\min_{v \in V} \max_{0 \le k \le n-1} \left\{ \frac{\delta'_n(s, v) - \delta'_k(s, v)}{n - k} \right\} = 0.$$

A path of exactly $k$ edges in $G'$ weighs $k \cdot \mu^*$ less than it did in $G$. Thus,

$$\delta'_k(s, v) = \delta_k(s, v) - k \mu^*.$$

Substituting this into the numerator:

$$\begin{align*} \delta'_n(s, v) - \delta'_k(s, v) &= (\delta_n(s, v) - n \mu^*) - (\delta_k(s, v) - k \mu^*) \\ &= \delta_n(s, v) - \delta_k(s, v) - (n - k)\mu^*. \end{align*}$$

Substitute this back into the fraction inside our max function:

$$\frac{\delta_n(s, v) - \delta_k(s, v) - (n - k)\mu^*}{n - k} = \frac{\delta_n(s, v) - \delta_k(s, v)}{n - k} - \mu^*.$$

Because $\mu^*$ is a constant that applies equally to every term, we can pull it completely outside of the max and min operators:

$$\left( \min_{v \in V} \max_{0 \le k \le n-1} \left\{ \frac{\delta_n(s, v) - \delta_k(s, v)}{n - k} \right\} \right) - \mu^* = 0.$$

g.

KARP-MIN-MEAN-CYCLE(G, w)
    n = |G.V|
    // Initialize a 2D table to store path weights of exact length k
    let delta[0..n, V] be a new table filled with infinity
    
    // Base case: 0 edges means a distance of 0 to start anywhere
    for each vertex v in G.V
        delta[0, v] = 0
        
    // DP: Compute delta_k(v) for all k from 1 to n
    for k = 1 to n
        for each edge (u, v) in G.E
            if delta[k-1, u] != infinity
                delta[k, v] = min(delta[k, v], delta[k-1, u] + w(u, v))
                
    // Compute the global minimum mean weight
    mu_star = infinity
    
    for each vertex v in G.V
        // Only consider vertices reachable in exactly n steps
        if delta[n, v] != infinity 
            max_fraction = -infinity
            
            // Find the max fraction for this specific vertex
            for k = 0 to n - 1
                if delta[k, v] != infinity
                    fraction = (delta[n, v] - delta[k, v]) / (n - k)
                    max_fraction = max(max_fraction, fraction)
            
            // Update the global minimum
            mu_star = min(mu_star, max_fraction)
            
    return mu_star

The total $O(VE)$ time assumes that $E=\Omega(V)$.

22-6 Bitonic shortest paths

Available in the latest revision of the IM.