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.

(Removed)

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$.

(Removed)

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.

(Removed)