Skip to content

24.5 Proofs of shortest-paths properties

24.5-1

Give two shortest-paths trees for the directed graph of Figure 24.2 (on page 648) other than the two shown.

Since the induced shortest path trees on $\{s, t, y\}$ and on $\{t, x, y, z\}$ are independent and have to possible configurations each, there are four total arising from that. So, we have the two not shown in the figure are the one consisting of the edges $\{(s, t), (s, y), (y, x), (x, z)\}$ and the one consisting of the edges $\{(s, t), (t, y), (t, x), (y, z)\}$.

24.5-2

Give an example of a weighted, directed graph $G = (V, E)$ with weight function $w: E \rightarrow \mathbb R$ and source vertex $s$ such that $G$ satisfies the following property: For every edge $(u, v) \in E$, there is a shortest-paths tree rooted at $s$ that contains $(u, v)$ and another shortest-paths tree rooted at $s$ that does not contain $(u, v)$.

Let $G$ have $3$ vertices $s$, $x$, and $y$. Let the edges be $(s, x)$, $(s, y)$, and $(x, y)$ with weights $1$, $1$, and $0$ respectively. There are $3$ possible trees on these vertices rooted at $s$, and each is a shortest paths tree which gives $\delta(s, x) = \delta(s, y) = 1$.

24.5-3

Embellish the proof of Lemma 24.10 to handle cases in which shortest-path weights are $\infty$ or $-\infty$.

To modify Lemma 24.10 to allow for possible shortest path weights of $\infty$ and $-\infty$, we need to define our addition as $\infty + c = \infty$, and $-\infty + c = -\infty$. This will make the statement behave correctly, that is, we can take the shortest path from $s$ to $u$ and tack on the edge $(u, v)$ to the end. That is, if there is a negative weight cycle on your way to $u$ and there is an edge from $u$ to $v$, there is a negative weight cycle on our way to $v$. Similarly, if we cannot reach $v$ and there is an edge from $u$ to $v$, we cannot reach $u$.

24.5-4

Let $G = (V, E)$ be a weighted, directed graph with source vertex $s$, and let $G$ be initialized by $\text{INITIALIZE-SINGLE-SOURCE}(G, s)$. Prove that if a sequence of relaxation steps sets $s.\pi$ to a non-$\text{NIL}$ value, then $G$ contains a negative-weight cycle.

Whenever $\text{RELAX}$ sets $\pi$ for some vertex, it also reduces the vertex's $d$ value. Thus if $s.\pi$ gets set to a non-$\text{NIL}$ value, $s.d$ is reduced from its initial value of $0$ to a negative number. But $s.d$ is the weight of some path from $s$ to $s$, which is a cycle including $s$. Thus, there is a negative-weight cycle.

24.5-5

Let $G = (V, E)$ be a weighted, directed graph with no negative-weight edges. Let $s \in V$ be the source vertex, and suppose that we allow $v.\pi$ to be the predecessor of $v$ on any shortest path to $v$ from source $s$ if $v \in V - \{s\}$ is reachable from $s$, and $\text{NIL}$ otherwise. Give an example of such a graph $G$ and an assignment of $\pi$ values that produces a cycle in $G_\pi$. (By Lemma 24.16, such an assignment cannot be produced by a sequence of relaxation steps.)

Suppose that we have a grap hon three vertices $\{s, u, v\}$ and containing edges $(s, u), (s, v), (u, v), (v, u)$ all with weight $0$. Then, there is a shortest path from $s$ to $v$ of $s$, $u$, $v$ and a shortest path from $s$ to $u$ of $s$ $v$, $u$. Based off of these, we could set $v.\pi = u$ and $u.\pi = v$. This then means that there is a cycle consisting of $u, v$ in $G_\pi$.

24.5-6

Let $G = (V, E)$ be a weighted, directed graph with weight function $w: E \rightarrow \mathbb R$ and no negative-weight cycles. Let $s \in V$ be the source vertex, and let $G$ be initialized by $\text{INITIALIZE-SINGLE-SOURCE}(G, s)$. Prove that for every vertex $v \in V_\pi$, there exists a path from $s$ to $v$ in $G_\pi$ and that this property is maintained as an invariant over any sequence of relaxations.

We will prove this by induction on the number of relaxations performed. For the base-case, we have just called $\text{INITIALIZE-SINGLE-SOURCE}(G, s)$. The only vertex in $V_\pi$ is $s$, and there is trivially a path from $s$ to itself. Now suppose that after any sequence of $n$ relaxations, for every vertex $v \in V_\pi$ there exists a path from $s$ to $v$ in $G_\pi$. Consider the $(n + 1)$th relaxation. Suppose it is such that $v.d > u.d + w(u, v)$. When we relax $v$, we update $v.\pi = u.\pi$. By the induction hypothesis, there was a path from $s$ to $u$ in $G_\pi$. Now $v$ is in $V_\pi$, and the path from $s$ to $u$, followed by the edge $(u,v) = (v.\pi, v)$ is a path from s to $v$ in $G_\pi$, so the claim holds.

24.5-7

Let $G = (V, E)$ be a weighted, directed graph that contains no negative-weight cycles. Let $s \in V$ be the source vertex, and let $G$ be initialized by $\text{INITIALIZE-SINGLE-SOURCE}(G, s)$. Prove that there exists a sequence of $|V| - 1$ relaxation steps that produces $v.d = \delta(s, v)$ for all $v \in V$.

Suppose we have a shortest-paths tree $G_\pi$. Relax edges in $G_\pi$ according to the order in which a BFS would visit them. Then we are guaranteed that the edges along each shortest path are relaxed in order. By the path-relaxation property, we would then have $v.d = \delta(s, v)$ for all $v \in V$. Since $G_\pi$ contains at most $|V| - 1$ edges, we need to relax only $|V| - 1$ edges to get $v.d = \delta(s, v)$ for all $v \in V$.

24.5-8

Let $G$ be an arbitrary weighted, directed graph with a negative-weight cycle reachable from the source vertex $s$. Show how to construct an infinite sequence of relaxations of the edges of $G$ such that every relaxation causes a shortest-path estimate to change.

Suppose that there is a negative-weight cycle $c = \langle v_0, v_1, \ldots, v_k \rangle$, where $v_0 = v_k$, that is reachable from the source vertex $s$; thus, $w(c) < 0$. Without loss of generality, $c$ is simple. There must be an acyclic path from $s$ to some vertex of $c$ that uses no other vertices in $c$. Without loss of generality let this vertex of $c$ be $v_0$, and let this path from $s$ to $v_0$ be $p = \langle u_0, u_1, \ldots, u_l \rangle$, where $u_0 = s$ and $u_l = v_0 = v_k$. (It may be the case that $u_l = s$, in which case path $p$ has no edges.)

After the call to $\text{INITIALIZE-SINGLE-SOURCE}$ sets $v.d = \infty$ for all $v \in V - \{s\}$, perform the following sequence of relaxations. First, relax every edge in path $p$, in order. Then relax every edge in cycle $c$, in order, and repeatedly relax the cycle. That is, we relax the edges $(u_0, u_1)$, $(u_1, u_2)$, $\ldots$, $(u_{l - 1}, v_0)$, $(v_0, v_1)$, $(v_1, v_2)$, $\ldots$, $(v_{k - 1}, v_0)$, $(v_0, v_1)$, $(v_1, v_2)$, $\ldots$, $(v_{k - 1}, v_0)$, $(v_0, v_1)$, $(v_1, v_2)$, $\ldots$, $(v_{k - 1}, v_0)$, $\ldots$

We claim that every edge relaxation in this sequence reduces a shortest-path estimate. Clearly, the first time we relax an edge $(u_{i - 1}, u_i)$ or $(v_{j - 1}, v_j)$, for $i = 1, 2, \ldots, l$ and $j = 1, 2, \ldots, k - 1$ (note that we have not yet relaxed the last edge of cycle $c$), we reduce $u_i.d$ or $v_j.d$ from $\infty$ to a finite value. Now consider the relaxation of any edge $(v_{j - 1}, v_j)$ after this opening sequence of relaxations. We use induction on the number of edge relaxations to show that this relaxation reduces $v_j.d$.

Basis: The next edge relaxed after the opening sequence is $(v_{k - 1}, v_k)$. Before relaxation, $v_k.d = w(p)$, and after relaxation, $v_k.d = w(p) + w(c) < w(p)$, since $w(c) < 0$.

Inductive step: Consider the relaxation of edge $(v_{j - 1}, v_j)$. Since $c$ is a simple cycle, the last time $v_j.d$ was updated was by a relaxation of this same edge. By the inductive hypothesis, $v_{j - 1}.d$ has just been reduced. Thus, $v_{j - 1}.d + w(v_{j - 1}, v_j) < v_j.d$, and so the relaxation will reduce the value of $v_j.d$.