BFS[续] 2(1-(2 区 日日回 r st u y Analysis Shortest path -Using aggregate analysis, the complexity E什么是最短路径【 definition? of BFS iS O(E+V SBy a BFS, we got a shortest-path distance E: Can you? d(s, v) from s to v as the minimum numbe of edges in any path from vertex s to vertex v Erlf there is no path from s to v, then 6(s,V)=00 Lemma 22.1 Lemma 22.2 iLemma 22.1. if (u, VEEIGI, then o(s, v) -After the BFS run on the graph G from a ≤6(s,u)+1【三角不等式】 given source vertex s, then upon termination for each vertex v in V Y Case 1. u is reachable from s. then the ≥dv≥6(s,V) distance from v is less than the length of the shortest path to u+(u, v), hence aCase 2 u is not reachable from s, then4 清华大学 宋斌恒 19 BFS[续] 1 0 2 3 2 1 2 ∞ v w r t u x y s Q={x,u} 1 0 2 3 2 1 2 3 v w r t u x y s Q={u,y} 清华大学 宋斌恒 20 BFS[续] 1 0 2 3 2 1 2 3 v w r t u x y s Q={y} 1 0 2 3 2 1 2 3 v w r t u x y s Q={} 清华大学 宋斌恒 21 Analysis Analysis Using aggregate analysis,the complexity of BFS is O(E+V). Can you? 清华大学 宋斌恒 22 Shortest path Shortest path 什么是最短路径【definition?】 By a BFS, we got a shortest-path distance δ(s,v) from s to v as the minimum number of edges in any path from vertex s to vertex v. If there is no path from s to v, then δ(s,v)=∞. 清华大学 宋斌恒 23 Lemma 22.1 Lemma 22.1 Lemma 22.1. if (u,v)∈E[G], then δ(s,v) ≤δ(s,u)+1【三角不等式】 Proof. Case 1. u is reachable from s, then the distance from v is less than the length of the shortest path to u + (u,v)，hence … Case 2. u is not reachable from s, then δ(s,u)=∞, hence … 清华大学 宋斌恒 24 Lemma 22.2 Lemma 22.2 After the BFS run on the graph G from a given source vertex s, then upon termination, for each vertex v in V, d[v]≥δ(s,v)