CSC263H1 Lecture 17: Lecture 17.docx

• School: UTSG
• Department: Computer Science
• Course: CSC263H1
• Professor: Toniann Pitassi

Document Summary

[v] = length of shortest path s v. Lemma 0: after bfs(s), v: (s,v) d[v] Theorem: after bfs(s), v: (s,v) = d[v] Lemma 1: if u enters the q before v, then d[u] g[v] After bfs(g,s) , nodes v of g, d[v] = (s,v) G and a node s of g after bfs(g,s), node x of g s. t. d[x] =/= (s,x) Let v e the closest node from s such that d[v] =/= (s,v) clearly (s,v) < d[v] (s,v) = (s,u) + 1 since u is closer than v to s, then by definition of v, (s,v) = d[u] d[v] > (s,v) = (s,u) + 1 = d[u] + 1 d[v] > d[u] + 1 * Consider the colour of v just before the bf explores node u. 3 possible cases: v is white so u discovers v so d[v] = d[u] + 1 a contra to , v is black v explored before u v enters q before u.