对于选出的顶点u,当他'同时'被前向搜索和后向搜索处理完成，或者说是‘同时’从
、
中删除了，此时可以结束。
当 Bi-Directional Search的结束的时候，如何找到最短路径？...={a(
),s(
),b(3),u(5)},
={t(0)}
向前搜索：从
中移除的最小值为
=3,执行边(a,b)的Relax操作，可得到
={u(5),b(6),t(
)},
={s(0),a(...3)}
向后搜索：从
中移除最小值为
=3,执行边(a,b)的Relax操作，可以计算出
={a(6),s(
),u(5)},
={t(0),b(3)}
向前搜索：从
中移除的最小值为
=5,执行边(...u,t)的Relax操作，可得到
={b(6),t(10)},
={s(0),a(3),u(5)}
向后搜索：从
中移除最小值为
=5,执行边(s,u)的Relax操作，可以计算出
={a(6),s(10...)},
={t(0),b(3),u(5)}
此时的u达到了终止的条件，同时从
和
中删除，按照前向搜索和后向搜索的指针去计算最短路径，发现为10，很明显不是最短路径。
云服务器
ICP备案
对象存储
腾讯会议
云直播
