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

Question

我正在实现一个 k-最短顶点不相交路径算法并且需要一个 寻找最短路径的快速算法。有负权重所以我不能 使用 dijkstra 和bellman-ford 是O(ne)。在我最近读到的一篇论文中，作者 使用所谓的 SPFA 算法来查找图中的最短路径 负权重，根据他们的说法，其复杂度为 O(e)。声音 有趣，但我似乎找不到有关该算法的信息。显然 这个：http://cnki.com.cn/Article_cn/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;

Answer 2

它实际上是一个很好的求最短路径的算法。它也被认为是队列重写的Bellmen-Ford算法。但在我看来，它像BFS。它的复杂度是O(ke)(e表示边数, k ≈ 2)。虽然我根本无法理解它，但它在大多数问题上都很快，特别是当只有很少的边时。

Func spfa(start, to) {
  dis[] = {INF}
  visited[] = false 
  dis[start] = 0
  // shortest distance
  visited[start] = true 
  queue.push(start)
  // push start point
  while queue is not empty {
    point = queue.front()
    queue.pop()
    visited[point] = false
    // marked as unvisited                    
    for each V from point {
      dis[V] = min(dis[V],dis[point] + length[point, V]);
      if visited[V] == false {
        queue.push(V)
        visited[V] = true
      }
    }
  }
  return dis[to]
}

获取路径和路径也很容易。更多的
希望能帮到你(●—●)来自OIer

Answer 3

Bellman-ford 可以处理负边。

SPFA 和 Bellman-ford 基本上是同一件事，因此它具有相同的最坏情况复杂性。

SPFA 是对 Bellman-ford 的优化。

看看我在 C++ 中针对 PS 的 SPFA 个人实现：

using namespace std;

const int INF = INT_MAX / 4;
struct node { int v, w; };
vector<int> SPFA(int max_v, int start_v, vector<vector<node>>&adj_list) {
    vector<int> min_dist(max_v + 1, INF);
    min_dist[start_v] = 0;
    queue<node> q; q.push({ start_v,0 });
    queue<int> qn; qn.push(0);
    while (q.size()) {
        node n = q.front(); q.pop();
        int nn = qn.front(); qn.pop();
        if (nn >= max_v) { printf("-1\n"); exit(0); }//negative cycle

        if (min_dist[n.v] < n.w) continue;
        min_dist[n.v] = n.w;

        for (node adj : adj_list[n.v]) {
            if (min_dist[adj.v] <= adj.w + n.w) continue;
            min_dist[adj.v] = adj.w + n.w;
            q.push({ adj.v, adj.w + n.w }), qn.push(nn + 1);
        }
    }
    return min_dist;
}

int main()
{
    // N: vertex cnt, M: edge cnt
    int N, M; scanf("%d%d", &N, &M);
    vector<vector<node>> adj_list(N + 1);
    for (int i = 0; i < M; i++) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);  // edge u->v, w:weigt
        adj_list[u].push_back({ v,w });
        //adj_list[v].push_back({ u,w }); in case of undirected graph
    }

    // shortest path from '1' to 'N'
    vector<int> dist = SPFA(N, 1, adj_list);
    printf("%d\n", dist[N]);
    return 0;
}