# Correctness of bft resulting in shortest path

I found the following proof concerning the correctness of a breadth-first traversal resulting in shortest path:

The key is that if we assume that we have a shorter path, we get a contradicition. I however do not fully understand with what the consequence of having a shorter path contradicts. Could someone explain it to me?

• Please edit your post to indicate where you saw that. We require you to credit the original source of all copied material: cs.stackexchange.com/help/referencing. I've shared this feedback before 1.
– D.W.
Commented Jun 24, 2022 at 7:43
• Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics. You can use LaTeX. Don't forget to give proper attribution to your sources!
– D.W.
Commented Jun 24, 2022 at 7:43
• What's a bft? Please define all terms in the question.
– D.W.
Commented Jun 24, 2022 at 7:44

The contradiction is that we're assuming the first time we've seen $$w$$ is through the node we're expanding, $$v$$. However, if there were a shorter path, then the second-to-last node in that path must be some other node, $$v'$$. Since the path is shorter, $$dist[v'] < dist[v]$$. But if that's the case then $$v'$$ should've been expanded prior to $$v$$, and we would've seen $$w$$ when that happened, contradicting our assumption.