正在加载图片...
广度优先搜索计算最短路长度 Why? 算法终止时v.d=8(s,v)for all v∈V 有什么价值? 证明要点:假设顶,点v是不满足上述条件的顶点中(s,V)值最小的 一个,针对v用反证法证明。 设u是从s到v的最短路上v的直接前驱点,则.d>8,)=86,)+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 O 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? 有什么价值?
<<向上翻页向下翻页>>
©2008-现在 cucdc.com 高等教育资讯网 版权所有