打开主菜单

最短路径快速算法

(重定向自SPFA算法

最短路径快速算法英语:Shortest Path Faster Algorithm (SPFA)),国际上一般认为是队列优化的贝尔曼-福特算法,是一个用于求解有向带权图单源最短路径的算法。这一算法被认为在随机的稀疏图上表现出色,并且适用于带有负边权的图。[1] 然而SPFA在最坏情况的时间复杂度与贝尔曼-福特算法相同,因此在非负边权的图中仍然最好使用戴克斯特拉算法[2] SPFA算法首先在1959年由Edward F. Moore英语Edward F. Moore作为广度优先搜索的扩展发表[3]。相同算法在1994年由段凡丁重新发现。[4]

目录

算法编辑

SPFA总的期望时间复杂度为 [5],基于实验获得的平均时间复杂度为 

给定一个有向带权图 和一个源点 ,SPFA算法计算从 到图中每个节点 的最短路径。对于每个节点 ,从   的最短路径表示为 

SPFA算法的基本思路与贝尔曼-福特算法相同,即每个节点都被用作用于松弛其相邻节点的备选节点。相较于贝尔曼-福特算法,SPFA算法的提升在于它并不盲目尝试所有节点,而是维护一个备选节点队列,并且仅有节点被松弛后才会放入队列中。整个流程不断重复直至没有节点可以被松弛。

下面是这个算法的伪代码。[6]这里的 是一个备选节点的先进先出队列,  是边 的权。

 
一个基于欧氏几何距离的SPFA算法。红线是当前状态下的各条最短路径。蓝线表示松弛发生的地方,也即通过在 中用节点 连接 可以给出一条从源点到 更短的路径
 procedure Shortest-Path-Faster-Algorithm(G, s)
  1    for each vertex vs in V(G)
  2        d(v) := ∞
  3    d(s) := 0
  4    offer s into Q
  5    while Q is not empty
  6        u := poll Q
  7        for each edge (u, v) in E(G)
  8            if d(u) + w(u, v) < d(v) then
  9                d(v) := d(u) + w(u, v)
 10                if v is not in Q then
 11                    offer v into Q

这个算法也可以通过将每条边换为两条逆向的边来用于无向图。

正确性证明编辑

https://web.archive.org/web/20130526103229/http://wcipeg.com/wiki/Shortest_Path_Faster_Algorithm

We will prove that the algorithm never computes incorrect shortest path lengths.

Lemma: Whenever the queue is checked for emptiness, any vertex currently capable of causing relaxation is in the queue.
Proof: We want to show that if  for any two vertices  and  at the time the condition is checked,  is in the queue. We do so by induction on the number of iterations of the loop that have already occurred. First we note that this certainly holds before the loop is entered: if , then relaxation is not possible; relaxation is possible from , and this is added to the queue immediately before the while loop is entered. Now, consider what happens inside the loop. A vertex  is popped, and is used to relax all its neighbors, if possible. Therefore, immediately after that iteration of the loop,  is not capable of causing any more relaxations (and does not have to be in the queue anymore). However, the relaxation by  might cause some other vertices to become capable of causing relaxation. If there exists some  such that  before the current loop iteration, then  is already in the queue. If this condition becomes true duringthe current loop iteration, then either  increased, which is impossible, or decreased, implying that  was relaxed. But after  is relaxed, it is added to the queue if it is not already present.
Corollary: The algorithm terminates when and only when no further relaxations are possible.
Proof: If no further relaxations are possible, the algorithm continues to remove vertices from the queue, but does not add any more into the queue, because vertices are added only upon successful relaxations. Therefore the queue becomes empty and the algorithm terminates. If any further relaxations are possible, the queue is not empty, and the algorithm continues to run.

The algorithm fails to terminate if negative-weight cycles are reachable from the source. See here for a proof that relaxations are always possible when negative-weight cycles exist. In a graph with no cycles of negative weight, when no more relaxations are possible, the correct shortest paths have been computed (proof). Therefore in graphs containing no cycles of negative weight, the algorithm will never terminate with incorrect shortest path lengths.

最坏情况下的性能编辑

下面是一种触发该算法低性能表现的数据构造方式。[1]假设要求从节点1到节点 的最短路径。对于整数 ,考虑添加边 并令其权为一个随机的小数字(于是最短路应为1-2-...- ),同时随机添加 条其他的权较大的边。在这种情况下,SPFA算法的性能表现将会非常低下。

优化技巧编辑

SPFA算法的性能很大程度上取决于用于松弛其他节点的备选节点的顺序。事实上,如果 是一个优先队列,则这个算法将极其类似于戴克斯特拉算法。然而尽管这一算法中并没有用到优先队列,仍有两种可用的技巧可以用来提升队列的质量,并且借此能够提高平均性能(但仍无法提高最坏情况下的性能)。两种技巧通过重新调整 中元素的顺序从而使得更靠近源点的节点能够被更早地处理。因此一旦实现了这两种技巧, 将不再是一个先进先出队列,而更像一个链表或双端队列。

距离小者优先Small Label First(SLF))(由Bertsekas在Networks, 第23期, 1993, 页703-709中最先提出)。在伪代码的第十一行,将总是把 压入队列尾端修改为比较  ,并且在 较小时将 压入队列的头端。这一技巧的伪代码如下(这部分代码插入在上面的伪代码的第十一行后):

 procedure Small-Label-First(G, Q)
     if d(back(Q)) < d(front(Q)) then
         u := pop back of Q
         push u into front of Q

距离大者置后Large Label Last(LLL))(由Bertsekas、Guerriero、与Musmanno在JOTA, 第88期, 1996, 页297-320最先提出)。在伪代码的第十一行,我们更新队列以确保队列头端的节点的距离总小于平均,并且任何距离大于平均的节点都将被移到队列尾端。伪代码如下:

 procedure Large-Label-Last(G, Q)
     x := average of d(v) for all v in Q
     while d(front(Q)) > x
         u := pop front of Q
         push u to back of Q

参见编辑

  1. ^ 1.0 1.1 About the so-called SPFA algorithm
  2. ^ SPFA算法 页面存档备份,存于互联网档案馆
  3. ^ Moore, Edward F. The shortest path through a maze. Proceedings of the International Symposium on the Theory of Switching. Harvard University Press: 285–292. 1959.  SPFA is Moore's “Algorithm D”.
  4. ^ SPFA算法详解. Leo Zhao 's blog. [2018-10-13]. 
  5. ^ Pacific. 如何卡spfa? - Pacific的回答 - 知乎. 2018-03-09 [2019-07-23]. 
  6. ^ http://codeforces.com/blog/entry/16221