1
$\begingroup$

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

source: https://people.eecs.berkeley.edu/~daw/teaching/cs170-s03/Notes/lecture6.pdf

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?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Commented Jun 24, 2022 at 7:43
  • 3
    $\begingroup$ 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! $\endgroup$
    – D.W. ♦
    Commented Jun 24, 2022 at 7:43
  • $\begingroup$ What's a bft? Please define all terms in the question. $\endgroup$
    – D.W. ♦
    Commented Jun 24, 2022 at 7:44

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.