0
$\begingroup$

I read in Algorithms in C by Sedgewick that we can easily prove by induction that breadth-first search algorithm computes the shortest path from one vertex to another (unweighted graphs or weighted graphs with edges = 1). I have written the proof below. Is it correct?

Statement S: Given two vertices $u$ and $y$, BFS computes the smallest amount of edges from $u$ to $y$.

Basis. If $u$ and $y$ are adjacent vertices, then there is one, and only one, edge connecting both. So the basis case clearly holds.

Induction. In inductive hypothesis, we assume that Statement S is true for $n$ edges and we want to prove that it is also true for $n + 1$ edges. BFS visits $u$ adjacent vertices, that is, $v_1, v_2, ..., v_k$, where $k$ is the amount of vertices. The $v_k$ vertices have $x_k$ adjacent vertices. If $x$ is the vertice we are looking for, then we have proved Statement S. Otherwise, we can visit all $x_k$ adjacent vertices with $n$ + 1 edges. We follow like this until we find $y$. When we visit $y$, there will be the smallest possible amount of edges from $u$ to $y$. Thus we have proved by induction that BFS always computes the smallest amount of edges from $u$ to $y$.

$\endgroup$
2
  • 2
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ Commented Jun 2, 2023 at 23:59
  • $\begingroup$ You may want to see Section 20.2 of CLRS for BFS for shortest path. $\endgroup$ Commented Jun 3, 2023 at 0:09

0

Your Answer

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