在Dijkstra算法中,面对单源单目标的最短路径,如果遇到了要relax的节点u就是目标节点t,显然就可以执行结束了。...Bi-Directional Search
具体操作位,从源点和从目标两个方向均开始搜索,轮流的执行。...对于选出的顶点u,当他'同时'被前向搜索和后向搜索处理完成,或者说是‘同时’从
、
中删除了,此时可以结束。
当 Bi-Directional Search的结束的时候,如何找到最短路径?...=3,执行边(a,b)的Relax操作,可得到
={u(5),b(6),t(
)},
={s(0),a(3)}
向后搜索:从
中移除最小值为
=3,执行边(a,b)的Relax操作,可以计算出
={...)}
向后搜索:从
中移除最小值为
=5,执行边(s,u)的Relax操作,可以计算出
={a(6),s(10)},
={t(0),b(3),u(5)}
此时的u达到了终止的条件,同时从
和
中删除,