广度优先搜索计算最短路长度 算法终止时v.d=6(s,v)for all v∈V 证明要点：假设顶，点v是不满足上述条件的定点中δ(S,V)值最小的 Why? 个，针对v用反证法证明。 设u是从s到v的最短路上v的直接前驱点，则.d>8,)8,0+1=u.d+1 Now consider the time when BFS chooses to dequeue vertex u from 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.du.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是不满足上述条件的定点中δ(s,v)值最小的 一个，针对v用反证法证明。 设u是从s到v的最短路上v的直接前驱点，则 Why？