最短路径快速算法 - Wikiwand
For faster navigation, this Iframe is preloading the Wikiwand page for 最短路径快速算法.

最短路径快速算法

维基百科,自由的百科全书

本條目存在以下問題,請協助改善本條目或在討論頁針對議題發表看法。 此條目使用外部链接的方式可能不符合维基百科的方针或指引,或致使內文成為链接農場。 (2019年5月21日)請協助清理過度與不適當的外部連結,并将有用的链接移到参考文献中。 此條目需要編修,以確保文法、用詞、语气、格式、標點等使用恰当。 (2018年7月22日)請按照校對指引,幫助编辑這個條目。(幫助、討論) 此條目翻譯品質不佳。 (2018年7月22日)翻譯者可能不熟悉中文或原文語言,也可能使用了機器翻譯,請協助翻譯本條目或重新編寫,并注意避免翻译腔的问题。明顯拙劣的機器翻譯請改掛((d|G13))提交刪除。

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

算法

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

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

一个基于欧氏几何距离的SPFA算法。红线是当前状态下的各条最短路径。蓝线表示松弛发生的地方,也即通过在
  
    
      
        Q
      
    
    {\displaystyle Q}
  
中用节点
  
    
      
        u
      
    
    {\displaystyle u}
  
连接
  
    
      
        v
      
    
    {\displaystyle v}
  
可以给出一条从源点到
  
    
      
        v
      
    
    {\displaystyle v}
  
更短的路径
一个基于欧氏几何距离的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

对于无向图,可通过将每个无向边视作两条有向边以采用 SPFA 算法。

最坏情况下的性能

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

由于SPFA算法本质上依然被认为是Bellman-Ford算法的一个特例,SPFA算法的最差复杂度依然被认为是,其中为边数,为点数。[1]

由于在NOI2018中被出题人使用特殊构造图卡到最坏情况,并在讲题时在ppt上打出关于SPFA他死了的字样,导致现今很多中国大陆OI题目都会卡掉SPFA,于是关于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 1.2 About the so-called SPFA algorithm. [2018-05-25]. (原始内容存档于2020-11-17). 
  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. ^ Duan, Fanding, 关于最短路径的SPFA快速算法, 西南交通大学学报 [Journal of Southwest Jiaotong University], 1994, 29 (2): 207–212 [2018-05-25], (原始内容存档于2019-04-25) 
  5. ^ 存档副本. [2018-05-25]. (原始内容存档于2021-01-16). 

扩展阅读

{{bottomLinkPreText}} {{bottomLinkText}}
最短路径快速算法
Listen to this article