最短路徑更快 - 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算法？

回答

相關問題