Key ideas on proving BFS gives the shortest path on unweighted undirected graphs

Basically some gists from http://www.cs.toronto.edu/~krueger/csc263h/lectures/BFS.pdf.

1
2
3
graph TD;
S-->U;
U-->V;

$d$: depth from root
$\delta$: shortest path from root


Prove by contradiction:
$v$: closest node ( to $s$) where $d[v]\neq \delta(s,v)$.
$u$: the “predecessor” of $d$ on one of the shortest paths from $s$ to $v$.
Statement to contradict with :

  • since predecessor, $\delta(s,u)+1=\delta(s,v)$.
  • since $v$ closest and $u$ closer, $d[v]=\delta(s,u)$.
  • from definition $d[v]\neq \delta(s,v)$.
  • therefore $d[v]\neq \delta(s,v)=\delta(s,u)+1$
  • since $d[v]$ is some kind of a path, and $\delta(s,v)$ is the shortest path by definition, $d[v]\geq \delta(s,v)$.
  • Combine last 2 step and $d[v]>d[u]+1$.

Remark: basically deduce that between reaching the predecessor on shortest path and the vertex, the BFS visits at least 2 other nodes.


Three cases:

  • $v$ not discovered:
    then $d[v]=d[u]+1$ since we will go to $v$ when exploring $u$’s neibours.

  • $v$ is discovered and explored:
    Then it is enqued before $u$ thus $d[v]\leq d[u]$1

  • $v$ discovered but not fully explored
    Take the node that discovered $v$, this node is explored before $u$
    so by it is enqueued before $u$1 $d[w]\leq d[u]$. Since $v$ discovered by $w$, $d[v]=d[w]+1\leq d[u]+1$


    Remark: the depth difference between $u$ and $v$ can’t be greater than 1 because we would explore all neighbours thus depth difference bettween neightbours cant be greater than $1$; and we know $u$ and $v$ have to be neighbours. Anyway the contradiction proof in other 2 cases uses property1 but it is pretty intuitive that the depth difference can only be smaller.


  1. 1.at any time if $v$ is enqueud after $u$ then $d(v)\geq d(u)$ Proof: use induction.

Key ideas on proving BFS gives the shortest path on unweighted undirected graphs

https://chiatzenw.github.io/2022/03/14/Key-ideas-on-proving-BFS-gives-the-shortest-path-on-unweighted-undirected-graphs/

Author

ChiatzenW

Posted on

2022-03-14

Updated on

2022-03-14

Licensed under

Comments