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

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

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

Bi-Directional Search

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

向前搜索：沿着源点向目标搜索

向后搜索：沿着目标向源点搜索

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

对于选出的顶点u,当他'同时'被前向搜索和后向搜索处理完成，或者说是‘同时’从$Q_f$、$Q_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_f$和$Q_b$中删除，按照前向搜索和后向搜索的指针去计算最短路径，发现为10，很明显不是最短路径。

正确的计算方式为：当终止之后，应该找到一个顶点x,使得$d_f[x]$+$d_b[x]$最小。具体措施为，看$S_f$、$Q_f$中的所有节点，看它在$S_b$、$Q_b$中值，使得$d_f[x]$+$d_b[x]$最小

另一种算法为Goal-Directed Search ,详见

转载地址：http://ronnx.baihongyu.com/

你可能感兴趣的文章