About the shortest-path estimates in “Introduction to Algorithms 3rd Edition” by CLRS(Cormen, Leiserson, Rivest, Stein).

Question

I am reading “Introduction to Algorithms 3rd Edition” by CLRS(Cormen, Leiserson, Rivest, Stein).

I cannot understand why the following statement holds in the proof of Lemma 24.16.

If $v_{i-1}.d$ changed since then, it decreased.
Therefore, just before the call $\text{RELAX}(v_{k-1}, v_k, w)$, we have $v_i.d \ge v_{i-1}.d + w(v_{i-1}, v_i)$ for all $i = 1, 2, \dots, k-1$.

I think $v_{i-1}.d$ never changes since then.

The followings are Lemma 24.16 and its proof:

Lemma 24.16

Let $G = (V, E)$ be a weighted, directed graph with weight function $w : E \to \mathbb{R}$,
let $s \in V$ be a source vertex, and assume that $G$ contains no negative-weight cycles that are reachable from $s$.

Then, after the graph is initialized by $\text{INITIALIZE-SINGLE-SOURCE}(G, s)$, the predecessor subgraph $G_\pi$ forms a rooted tree with root $s$, and any sequence of relaxation steps on edges of $G$ maintains this property as an invariant.

Proof

Initially, the only vertex in $G_\pi$ is the source vertex, and the lemma is trivially true.

Consider a predecessor subgraph $G_\pi$ that arises after a sequence of relaxation steps.

We shall first prove that $G_\pi$ is acyclic.

Suppose for the sake of contradiction that some relaxation step creates a cycle in the graph $G_\pi$.

Let the cycle be $c = <v_0, v_1, \dots v_k>$, where $v_k = v_0$.

Then, $v_i.\pi = v_{i-1}$ for $i = 1, 2, \dots, k$ and, without loss of generality, we can assume that relaxing edge $(v_{k_1}, v_k)$ created the cycle in $G_\pi$.

We claim that all vertices on cycle $c$ are reachable from the source $s$.

Why?

Each vertex on $c$ has a non-NIL predecessor, and so each vertex on $c$ was assigned a finite shortest-path estimate when it was assigned its non-NIL $\pi$ value.

By the upper-bound property, each vertex on cycle $c$ has a finite shortest-path weight, which implies that it is reachable from $s$.

We shall examine the shortest-path estimates on $c$ just prior to the call $\text{RELAX}(v_{k-1}, v_k, w)$ and show that $c$ is a negative-weight cycle, thereby contradicting the assumption that $G$ contains no negative-weight cycles that are reachable from the source.

Just before the call, we have $v_i.\pi = v_{i-1}$ for $i = 1, 2, \dots, k-1$.

Thus, for $i = 1, 2, \dots, k - 1$, the last update to $v_i.d$ was by the assignment $v_i.d = v_{i-1}.d + w(v_{i-1}, v_i)$. If $v_{i-1}.d$ changed since then, it decreased.

Therefore, just before the call $\text{RELAX}(v_{k-1}, v_k, w)$, we have $v_i.d \ge v_{i-1}.d + w(v_{i-1}, v_i)$ for all $i = 1, 2, \dots, k-1$.

$\dots$

Answer 1

In the shortest-path algorithm, $v_k.d$ is only changed if we can find a new path with a smaller distance from the source.

Thus, for $i=1,2,…,k−1$, the last update to $v_i.d$ was by the assignment $v_i.d=v_{i−1}.d+w(v_{i−1},v_i)$.

At this point, $v_{i - 1}$, and in turn, $v_i$ have the shortest path from the source. We will only update $v_i.d$ if we have found an even shorter path from the source to $v_{i - 1}$. Hence,

If $v_{i−1}.d$ changed since then, it decreased.

Now, just before we perform RELAXation at vertex $v_i$, it has a distance from the source that may be larger than what $v_{i - 1} + w(v_{i - 1}, v_i)$ equals. That is because we may have updated $v_{i - 1}.d$ but have not yet updated $v_i.d$. Thus, the following holds

Therefore, just before the call $\mathrm{RELAX}(v_{k−1},v_k,w)$, we have $v_i.d\ge v_{i−1}.d+w(v_{i−1},v_i)$ for all $i=1,2,…,k−1$.