Proof that BFS finds shortest distance

Intuitively, Breadth-First Search (BFS) can find shortest distances from a source $latex s&s=4$ to any other reachable vertex. However, proving this intuition needs a bit hard work. After some searches, I found that there are two ideas to prove it. The two ideas both use induction to prove it. Both ideas require a bit long proof.

  1. The first idea is based on CLRS Page 597-600. The second reference below is talking about the same idea.
  2. The second idea is from a pdf file from NYU.  (the third reference)

References:

Here I am showing my proof, a small variant of CLRS:

extra_Page_2extra_Page_3

Leave a comment

Your email address will not be published. Required fields are marked *