最短路径更快 - 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）。

这是维基百科的中文伪代码，您也可以在其中找到 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;