查看“︁最短路径快速算法”︁的源代码

{{多個問題|
{{external links|time=2019-05-21T02:08:27+00:00}}
{{copyedit|time=2018-07-22T11:44:54+00:00}}
{{roughtranslation|time=2018-07-22T11:44:54+00:00}}
}}
{{NoteTA
|G1 = IT
}}
'''最短路径快速算法'''（{{lang-en|Shortest Path Faster Algorithm (SPFA)}}），国际上一般认为是带有队列优化的[[贝尔曼-福特算法|Bellman-Ford 算法]]，一般仅在中国大陆被称为'''SPFA'''，是一个用于求解有向带权图单源最短路径的算法。这一算法在随机的稀疏图上表现出色，并且适用于带有负边权的图。<ref name="poj">{{Cite web |url=http://poj.org/showmessage?message_id=136458 |title=About the so-called SPFA algorithm |access-date=2018-05-25 |archive-date=2020-11-17 |archive-url=https://web.archive.org/web/20201117070719/http://poj.org/showmessage?message_id=136458 |dead-url=no }}</ref> 然而SPFA在最坏情况的时间复杂度与 Bellman-Ford 算法相同，因此在非负边权的图中使用堆优化的[[戴克斯特拉算法|Dijkstra 算法]]效率可能优于SPFA。<ref name="nocow">[http://www.nocow.cn/index.php/SPFA SPFA算法] {{Wayback|url=http://www.nocow.cn/index.php/SPFA |date=20120702205722 }}</ref> SPFA算法首先在1959年由{{link-en|Edward F. Moore|Edward F. Moore}}作为[[广度优先搜索]]的扩展发表<ref>{{cite conference|first=Edward F.|last=Moore|authorlink=Edward F. Moore|year=1959|contribution=The shortest path through a maze|title=Proceedings of the International Symposium on the Theory of Switching|publisher=Harvard University Press|pages=285–292}}  SPFA is Moore's “Algorithm D”.</ref>，相同算法在1994年由段凡丁重新发现。<ref name="duan">{{Citation
| last=Duan
| first=Fanding
| year=1994
| title=关于最短路径的SPFA快速算法
| journal=西南交通大学学报 [Journal of Southwest Jiaotong University]
| volume=29
| issue=2
| pages=207–212
| url=http://wenku.baidu.com/view/3b8c5d778e9951e79a892705.html
| accessdate=2018-05-25
| archive-date=2019-04-25
| archive-url=https://web.archive.org/web/20190425210629/https://wenku.baidu.com/view/3b8c5d778e9951e79a892705.html
| dead-url=no
}}</ref> 

== 算法 ==
给定一个有向带权图<math> G=(V,E) </math>和一个源点<math> s </math>，SPFA算法可以计算从<math> s </math>到图中每个节点<math> v </math>的最短路径。其基本思路与 Bellman-Ford 算法相同，即每个节点都被用作用于松弛其相邻节点的备选节点。但相较于 Bellman-Ford 算法，SPFA算法的先进之处在于它并不盲目地尝试所有节点，而是维护一个备选的节点队列，并且仅有节点被松弛后才会将其放入队列中。整个流程不断重复，直至没有节点可以被松弛。

下面是这个算法的[[伪代码]]。<ref name="codeforce">{{Cite web |url=http://codeforces.com/blog/entry/16221 |title=存档副本 |access-date=2018-05-25 |archive-date=2021-01-16 |archive-url=https://web.archive.org/web/20210116004221/https://codeforces.com/blog/entry/16221 |dead-url=no }}</ref>这里的<math> Q </math>是一个备选节点的先进先出队列，<math> w(u,v) </math> 是边<math> (u,v) </math>的权值。
[[File:SPFADemo.gif|thumb|一个基于欧氏几何距离的SPFA算法。红线是当前状态下的各条最短路径。蓝线表示松弛发生的地方，也即通过在<math> Q </math>中用节点<math> u </math>连接<math> v </math>可以给出一条从源点到<math> v </math>更短的路径]]

  '''procedure''' Shortest-Path-Faster-Algorithm(''G'', ''s'')
   1    '''for''' each vertex ''v'' ≠ ''s'' 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''

对于无向图，将每条无向边视作两条有向边以采用 SPFA 算法。

== 最坏情况下的性能 ==

下面是一种触发该算法低性能表现的数据构造方式。假设要求从节点1到节点<math>n</math>的最短路径。对于整数<math> 1\leq i<n </math>，考虑添加边<math> (i,i+1) </math>并令其权为一个随机的小数字（于是最短路应为1-2-...-<math> n </math>），同时随机添加<math> 4n </math>条其他的权较大的边。在这种情况下，SPFA算法的性能表现将会非常低下。<ref name="poj"/>

SPFA算法本质上依然被认为是Bellman-Ford算法的一个特例，因此一般认为SPFA算法的最差复杂度是<math>O(|V|\cdot|E|)</math>，其中<math>|V|</math>为点数，<math>|E|</math>为边数。<ref name="poj" />

== 优化技巧 ==

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

'''距离小者优先''' （'''Small Label First'''('''SLF''')）（由Bertsekas在Networks, 第23期, 1993, P703-P709中最先提出)。在伪代码的第十一行，将总是把<math> v </math>压入队列尾端修改为比较<math> d(v) </math> 和 <math> d\big(\text{front}(Q)\big) </math>，并且在<math> d(v) </math>较小时将<math> v </math>压入队列的头端。这一技巧的伪代码如下（这部分代码插入在上面的伪代码的第十一行后）：

  '''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''

== 参考文献 ==
{{Reflist}}

== 扩展阅读 ==
* {{cite journal |author1=夏正冬 |author2=卜天明 |author3=张居阳 |title=SPFA算法的分析及改进 |journal=《计算机科学》 |date=2014 |volume=41 |issue=6 |pages=180-184 |url=http://www.cnki.com.cn/Article/CJFDTotal-JSJA201406035.htm |accessdate=2020-11-17 |archive-date=2020-12-08 |archive-url=https://web.archive.org/web/20201208203225/http://www.cnki.com.cn/Article/CJFDTOTAL-JSJA201406035.htm |dead-url=no }}

[[Category:图算法]]