最短路径更快 - SPFA算法？-Java 学习之路

我正在实现一个k最短的顶点不相交路径算法，需要一个快速算法来找到最短路径 . 有负权重，所以我不能使用dijkstra和bellman-ford是O（ne） . 在我最近阅读的一篇论文中，作者使用所谓的SPFA算法来找到负权重图中的最短路径，根据它们，它具有O（e）的复杂度 . 听起来很有趣，但我似乎无法找到有关该算法的信息 . 显然这个：http://en.cnki.com.cn/Article_en/CJFDTOTAL-XNJT402.015.htm是原始论文，但我无法访问它 .

有没有人有这个算法的良好信息或实施？此外，是否有任何k-shortest顶点不相交路径问题的来源？我找不到任何东西 .

谢谢！

2 回答

0
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;
```
回复于 2024-04-23T14:53:13+08:00

找出最短路径实际上是一个很好的算法 . 它也被认为是由队列重写的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

回复于 2024-04-23T14:53:13+08:00

最短路径更快 - SPFA算法？

2 回答

相关问题