Question about step in proof that predecessor subgraph forms a breadth-first tree

Question

Given the following theorem and definitions from Introduction to Algorithms 3rd edition by CLRS:

Theorem 22.5: (Correctness of breadth-first search)

Let $G = (V, E)$ be a directed or undirected graph, and suppose that $BFS$ is run on $G$ from a given source vertex $s \in V$. Then, during its execution, $BFS$ discovers every vertex $v \in V$ that is reachable from the source $s$, and upon termination, $v.d = \delta(s, v)$ for all $v \in V$. Moreover, for any vertex $v \neq s$ that is reachable from $s$, one of the shortest paths from $s$ to $v$ is a shortest path from $s$ to $v.\pi$ followed by the edge $(v.\pi, v)$.

$\delta(s,v) \rightarrow \text{length of the shortest path from s to v} \\\ v.d\rightarrow \text{distance assigned to vertex $v$ from $s$ by BFS}\\\ v.\pi\rightarrow \text{predecessor of $v$ in the path from $s$ to $v$ in the BFS}$

For a graph $G = (V, E)$ with source $s$, the predecessor subgraph of $G$ is $G_{\pi} = (V_{\pi}, E_{\pi})$, where $V_{\pi} = \{ v \in V : v.\pi \neq NIL\} \cup \{s\}$ and $E_{\pi} = \{ (v.\pi, v) : v \in V_{\pi} - \{s\}\}$

The predecessor subgraph $G_{\pi} = (V_{\pi}, E_{\pi})$ is a breadth-first tree if $V_{\pi}$ consists of the vertices reachable from $s$ and, for all $v \in V_{\pi}$, the subgraph $G_{\pi}$ contains a unique simple path from $s$ to $v$ that is also a shortest path from $s$ to $v$ in $G$

I have a question about the following proof:

Lemma 22.6:

When applied to a directed or undirected graph $G = (V, E)$, procedure BFS constructs $\pi$ so that the predecessor subgraph $G_{\pi} = (V_{\pi}, E_{\pi})$ is a breadth-first tree.

Line 16 of BFS sets $v.\pi = u$ iff $(u, v) \in E$ and $\delta(s, v) < \infty$ - that is, if $v$ is reachable from $s$- and thus $V_{\pi}$ consists of the vertices in $V$ reachable from $s$. Since $G_{\pi}$ forms a tree, it contains a unique simple path from $s$ to each vertex in $V_{\pi}$. By applying Theorem 22.5 inductively, we conclude that every such path is a shortest path in $G$.

I'm not sure I understand the last sentence of this proof. Can anyone elaborate on how to "apply Theorem 22.5 inductively" to "conclude that every such path is a shortest path in $G$"?

Update:

One interpretation might be that we need to use induction to prove the last claim and the last part of Theorem 22.5 about a shortest path from $v.\pi$ to $v$is used in the proof.

For example, we can order the vertices in $V_{\pi}$ in non-decreasing order of distances from $s$. The base case would be the first vertex in $V_{\pi}$, which is $s$. We then assume that it holds for the first $n$ vertices in $V_{\pi}$ and we show that it holds for $v_{n+1}$ by appealing to the last part of Theorem 22.5.

Answer 1

Your update is correct. On first reading I thought it was wrong because distances can be negative. It's early here for me ... then I remembered that CLRS defines distance from $s$ to $v$ to be the minimum number of edges on any path from $s$ to $v$ when discussing BFS. Indeed, here is a simple proof:

The proof is by induction on the length (number of edges) of a path from $s$ in $G_\pi$, with hypothesis $H(n)$ that for any path $P = s \leadsto v \in G_\pi$ such that the length of $P$ is at most $n$, $P$ is a shortest path in $G$. The base case when $n = 0$ is trivial. For the step assume $H(k)$ for some $k \in \mathbb{N}$, let $n=k+1$ and let $P = s \leadsto v.\pi \leadsto v \in G_\pi$ be a path of length $k+1$, where $s$ and $v.\pi$ may be the same vertex. $H(k)$ implies that the path $P' = s \leadsto v.\pi$ is a shortest path in $G$. Applying Theorem 22.5, we conclude that $P$ is also a shortest path in $G$, which completes the induction.