最短路径更快 - SPFA算法？

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

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

谢谢！

来源

2011-10-10 sd_

SPFA算法是对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;

来源

2012-02-11 22:44:30

它实际上是一个很好的算法，找出最短path.It也算是行李员-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

来源

2016-01-24 13:36:06 ljt12138

最短路径更快 - SPFA算法？

回答

相关问题