广度优先搜索计算最短路长度 算法终止时.d=8(s,)for all v∈V 证明要点：假设顶点v是不满足上述条件的定点中.d值最小的一 个，针对v用反证法证明。 设u是从s到v的最短路上v的直接前驱点，则.d>6s,)86,W)+1=u.d+1 Now consider the time when BFS chooses to dequeue vertex u from o in line 11.At this time,vertex v is either white,gray,or black.We shall show that in each of these cases,we derive a contradiction to inequality (22.1).If v is white,then line 15 sets v.d =u.d+1,contradicting inequality (22.1).If v is black,then it was already removed from the queue and,by Corollary 22.4,we have v.d <u.d,again contradicting inequality (22.1).If v is gray,then it was painted gray upon dequeuing some vertex w,which was removed from earlier than u and for which v.d w.d+1.By Corollary 22.4,however,w.d <u.d,and so we have v.d=w.d+1<u.d+1,once again contradicting inequality (22.1).广度优先搜索计算最短路长度 算法终止时 证明要点：假设顶点 v是不满足上述条件的定点中.d值最小的一 个，针对 v用反证法证明。 设 u是从 s 到 v的最短路上v的直接前驱点，则 Why ？