graph - 最短路径更快 - SPFA 算法？

Question

我正在实现一个 k 最短顶点不相交路径算法并且需要一个
寻找最短路径的快速算法。有负权重所以我不能
使用 dijkstra 和 bellman-ford 是 O(ne)。在我最近读到的一篇论文中，作者
使用所谓的SPFA算法在图中找到最短路径
负权重，根据他们的说法，其复杂度为 O(e)。声音
有趣，但我似乎无法找到有关该算法的信息。显然
此:http://en.cnki.com.cn/Article_en/CJFDTOTAL-XNJT402.015.htm是原版
纸，但我无法访问它。

有没有人有很好的信息或者这个算法的实现？
另外，是否有可用的 k 最短顶点不相交路径问题的任何来源？
我找不到任何东西。

谢谢!

Answer 1

SPFA 算法是对 Bellman-Ford 的优化。而在 Bellman-Ford 中，我们只是盲目地通过每条边来获得 |V|轮次，在SPFA中，维护一个队列以确保我们只检查那些松弛的顶点。这个想法类似于 Dijkstra 的。它也与 BFS 具有相同的风格，但一个节点可以多次放入队列中。

源首先添加到队列中。然后，当队列不为空时，从队列中弹出一个顶点 u，我们查看它的所有邻居 v。如果 v 的距离发生变化，我们将 v 添加到队列中(除非它已经在队列中) .

作者证明了SPFA通常很快(\Theta(k|E|)，其中k < 2)。

这是来自 wikipedia in Chinese 的伪代码，您还可以在其中找到 C 语言的实现。

Procedure SPFA;
Begin
  initialize-single-source(G,s);
  initialize-queue(Q);
  enqueue(Q,s);
  while not empty(Q) do 
    begin
      u:=dequeue(Q);
      for each v∈adj[u] do 
        begin
          tmp:=d[v];
          relax(u,v);
          if (tmp<>d[v]) and (not v in Q) then
            enqueue(Q,v);
        end;
    end;
End;