I am reading CLRS (https://pd.daffodilvarsity.edu.bd/course/material/book-430/pdf_content), and stuck on the proof of Theorem 22.5 - Correctness of Breadth First Search on Page 600.
The author is trying to prove that for every vertex π£ reachable from source π in the graph, BFS sets π£.π = Ξ΄(π , π£), where π£.π is the shortest distance found by BFS for π£ and Ξ΄(π , π£) is the shortest distance from π to π£. But a step in the proof assumes the above property to be true for some neighbor vertex π’ of π£, giving the reason as "because of how we chose π£":
I'm sure that I am missing something here.
What is special in the way that π£ is chosen that allows us to assume the above mentioned property for some neighbor π’ of π£?
But a step in the proof assumes the above property to be true for some neighbor vertex u of v
Not just some neighbor of π£, but a neighbor that precedes π£ on the breadth-first path to it. Quoting the text:
Let π’ be the vertex immediately preceding π£ on a shortest path from π to π£, so that Ξ΄(π ,π£) = Ξ΄(π ,π’) + 1. Because Ξ΄(π ,π’) < Ξ΄(π ,π£), and because of how we chose π£, we have π’.π = Ξ΄(π ,π’).
"how we chose π£" refers to the following:
Let π£ be the vertex with minimum Ξ΄(π ,π£) that receives such an incorrect π value;
The key word here is "minimum". This means that π’, which is closer to π than π£ is, cannot have an incorrect π, otherwise π£ wasn't the minimum one. So we trust π’.π to be Ξ΄(π ,π’).