专栏名称: 爬蜥
目录
相关文章推荐
51好读  ›  专栏  ›  爬蜥

如何加快Dijkstra算法的运行速度?

爬蜥  · 掘金  ·  · 2018-07-07 15:19

正文

请到「今天看啥」查看全文


阅读 3

如何加快Dijkstra算法的运行速度?

算法导论(MIT 6.006 第18讲)

如何加快Dijkstra算法的运行速度?

在Dijkstra算法中,面对单源单目标的最短路径,如果遇到了要relax的节点u就是目标节点t,显然就可以执行结束了。

Dijkstra算法

Dijkstra算法的探索路径是从源一直往目标前景,那么加速它的一个角度就是从源开始探索的时候,同时从目标点向源开始探索,这种算法即Bi-Directional Search。

Bi-Directional Search

具体操作位,从源点和从目标两个方向均开始搜索,轮流的执行。两个方向的搜索意味着,在初始化的时候将有两个路径值: d_f[u] :向前搜索最短路径、 d_b[u] 向后搜索最短路径;两个最小优先级队列 Q_fQ_b ;对应的前一个节点指向 \pi_f\pi_b ;以及 S_fS_b

  • 向前搜索:沿着源点向目标搜索
  • 向后搜索:沿着目标向源点搜索

Bi-Directional Search的结束条件是什么?

对于选出的顶点u,当他'同时'被前向搜索和后向搜索处理完成,或者说是‘同时’从 Q_fQ_b 中删除了,此时可以结束。

当 Bi-Directional Search的结束的时候,如何找到最短路径?

可能想到的思路是,如果u是第一个满足结束条件的,那么沿着各自的前向指针,即可找到最短路径。以如下搜索为例:

向前搜索 :从源点出发,使用Dijkstra算法,可以计算出 Q_f ={a(3),u(5),b( \infty ),t( \infty )}, S_f ={s(0)}

向后搜索 :从目标出发,使用Dijkstra算法,可以计算出 Q_b ={a( \infty ),s( \infty ),b(3),u(5)}, S_b ={t(0)}

向前搜索 :从 Q_f 中移除的最小值为 d_f[a] =3,执行边(a,b)的Relax操作,可得到 Q_f ={u(5),b(6),t( \infty )}, S_f ={s(0),a(3)}

向后搜索 :从 Q_b 中移除最小值为 d_b[b] =3,执行边(a,b)的Relax操作,可以计算出 Q_b ={a(6),s( \infty ),u(5)}, S_b ={t(0),b(3)}

向前搜索 :从 Q_f 中移除的最小值为 d_f[u] =5,执行边(u,t)的Relax操作,可得到 Q_f ={b(6),t(10)}, S_f ={s(0),a(3),u(5)}

向后搜索 :从 Q_b 中移除最小值为 d_b[u] =5,执行边(s,u)的Relax操作,可以计算出 Q_b ={a(6),s(10)}, S_b ={t(0),b(3),u(5)}

此时的u达到了终止的条件,同时从 Q_fQ_b 中删除,按照前向搜索和后向搜索的指针去计算最短路径,发现为10,很明显不是最短路径。
正确的计算方式为:当终止之后,应该找到一个顶点x,使得 d_f[x] + d_b[x] 最小。具体措施为,看 S_fQ_f 中的所有节点,看它在 S_bQ_b 中值,使得 d_f[x] + d_b[x] 最小

另一种算法为Goal-Directed Search ,详见 https://www.researchgate.net/publication/225722939_Speed-Up_Techniques_for_Shortest-Path_Computations







请到「今天看啥」查看全文