小步最短路径算法

      小步最短路径算法的路径值在每次迭代中，只增加最小的量，以使得确定路径值的节点数量不为0且最少，可一次性确定一个或多个节点的所有最短路径。 相比Dijkstra算法，小步最短路径算法会显著降低计算量，且能充分利用硬件的高并行能力。

      现有最短路径算法主要建立在基于松弛操作的Dijkstra算法之上。设S为已经找到最短路径的节点集，Q为还未找到最短路径的节点集。Dijkstra算法对最近加入S中的节点u，考察每个与u相连且不在S中的节点v，即在dist[u]+length(u,v)<dist[v]时，v的权重值dist[v]被dist[u]+length(u,v)替换，v的路径前驱pre[v]指向u。

      因此，Dijkstra算法存在如下缺陷：（1）用松弛操作为Q中节点在多个路径之间不断地选择权重值更小的路径，会重复更新Q中某些节点的路径信息，具体表现在：Q中节点的路径信息在多次迭代之间可能被更新；在每次迭代中对dist的扰动程度与u的出度正相关。以上两点使得新生成的u在Q中的维护成本大幅增加。（2）节点u的邻接边需要很多的条件判断，严重依赖CPU的算术逻辑单元，无法高效地利用并行计算提高计算机系统运行最短路径算法的效率。 

      小步最短路径算法的路径值在每次迭代中，只增加最小的量，以使得确定路径值的节点数量不为0且最少，可一次性确定一个或多个节点的所有最短路径，其具体过程为：

      S1，初始化迭代起点的路径值pathlength为0；

      S2，pathlength增加最小的值，以使得至少一个节点确定最短路径；

      S3，重复执行S2，直到所有节点都确定了最短路径。

图一

图二

      设图一中节点h为迭代起点，到其他节点的最短路径为图二中所示路径，其中节点b 有两条长度为13的最短路径。

      Dijkstra算法更新节点的路径过程为：

      1. 初始化时，更新节点h的路径信息=0，pathlength=0；

      2. 确定节点h的最短路径=0，在处理节点h时，更新节点f的路径=3，更新节点g的路径信息=4；

黑实线表示节点路径值发生更新

      3. 确定节点f的最短路径=3，在处理节点f时，会更新节点b的路径信息=13，会更新节点e的路径信息=11，g的路径信息不变；

虚线表示更失败

      4. 确定节点g的最短路径=4，在处理节点g时，会更新节点d的路径信息=12，会更新节点e的路径信息=6，邻接节点f已确定最短路径；

删除的黑实线<f,e>表示该更新被其他更新替换

      5. 确定节点e的最短路径=6，在处理节点e时，为节点b新增一条路径为13的路径，会更新节点a的路径信息=12，会更新节点d的路径信息=12，邻接节点f已确定最短路径；

节点b存在两条等长最短路径

      6. 确定节点a/d的最短路径=12，在处理节点a/d时，不需要更新任何节点的路径信息；

邻接边<a,d>和<a,b>状态共享先处理a的情形

      7. 确定节点b的最短路径=13，在处理节点b时，不需要更新任何节点的路径信息。

      小步最短路径算法更新节点的路径过程为：

1. 初始化时，更新节点h的最短路径信息=0；
2. Pathlength最小增加到3，确定节点f的最短路径=3，邻接边<h,f>变为已处理（在确定的最短路径中的邻接边）；
3. Pathlength最小增加到4，确定节点g的最短路径=4，邻接边<h,g>变为已处理，邻接边<f,g>变为无效（不在任何最短路径中的已处理邻接边）；
4. Pathlength最小增加到6，确定节点e的最短路径=6，邻接边<e,g>变为已处理，邻接边<f,e>变为无效；
5. Pathlength最小增加到12，确定节点a/d的最短路径=12，邻接边<e,a>/<d,g>变为已处理，邻接边<d,e>和<a,d>变为无效；
6. Pathlength最小增加到13，确定节点b的最短路径=13，邻接边<e,b>/<b,f>变为已处理，邻接边<a,b>变为无效。

      小步最短路径算法，确定的路径信息都是最短路径，且在每次迭代中得到所有长度相同的最短路径。在具体实现时，可把节点的邻接边边按权重值升序排列，以提高运行的效率。并通过一个集合，跟踪确定最短路径但存在未处理邻接边的节点，这是小步算法引入的新的计算量，需要用一个最小堆维护下个确定最短路径的节点，其复杂度与Dijkstra算法中维护Q的复杂度相同。

      小步最短路径算法具有巨大并发优势，可并行计算多个节点的最短路径。如存在k*n个等长的最短路径时，可通过k个线程并发处理。

      小步最短路径算法通过避免无效的节点路径更新，可显著降低计算量。Dijkstra算法在确定一个节点的最短路径后，会尝试更新所有在Q中的邻接节点的路径值；而小步算法在确定一个节点的最短路径后，不会更新任何人和节点的路径值。在上例中，Dijkstra算法尝试次更新路径值的次数与边的数量正相关，而小步最短路径算法更新路径值的次数与节点数量正相关。

       该方法对于权重为负值的图，做路径的回退后，也是适用的。

参考文献：

专利GAI22CN4390