Dijkstra的負權重算法（但沒有負循環）

我相信下面的Dijkstra算法的實現適用於所有負權重但沒有負和的循環。Dijkstra的負權重算法（但沒有負循環）

但是，我看到很多人說Dijkstra對於負權重圖不起作用，所以我相信算法是錯誤的或者執行時間比Dijkstra算法慢得多。

我只是想知道如果有人可以請幫我這個代碼？非常感謝您的幫助！

（編輯：這個問題是別人不一樣，因爲我也想知道如果該算法的執行時間遠遠大於Dijkstra算法較長時間，因爲節點可以多次訪問）

#include <bits/stdc++.h> 
using namespace std; 

vector<pair<int, int> > G[N]; 
int cost[N]; 
int main() { 

    queue<int> q; 
    q.push(0); 
    cost[0] = 0; 
    for(int i=1; i<N; i++) { 
     cost[i] = infinity; 
    } 

    while(! q.empty()) { 
     int v = q.front(); 
     q.pop(); 

     for(int i=0; i<G[v].size(); i++) { 
      if(cost[G[v][i].first] > cost[v] + G[v][i].second) { 
       cost[G[v][i].first] = cost[v] + G[v][i].second; 
       q.push(G[v][i].first); 
      } 
     } 
    } 
}

來源

2017-08-18 user8384788

可能使用[使用Dijkstra算法的負權重]（https://stackoverflow.com/questions/6799172/negative-weights-using-dijkstras-algorithm） –

可能，但在第一個答案的圖中，此算法給出正確的重量（-200）。此外，我想知道如果可能這種算法，因爲它多次訪問每個節點，執行所需的時間比Dijkstra的多得多。 – user8384788

這是正確的，但在最壞的情況下它是指數級的。不過，我不記得如何建立這樣一個圖表的例子。 – kraskevich

即使正確（沒有證明它，但它似乎是），你的算法遭受時間複雜性不好。

特別是，如果你看一個完整的DAG：

G = (V, E, w) 
V = {1, ..., n} 
E = { (i,j) | i < j } 
w(u,v) = 2^ (v - u)

而對於例如簡單起見，我們假設算法（(u,x)如果x < v前(u,v)）遍歷以相反的順序邊緣（請注意，這只是簡化，甚至沒有它你可以通過反轉邊緣的方向來建立一個反例）。

請注意，每次打開它時，您的算法都會重新打開每條邊。這意味着您遍歷此圖中的所有路徑，其中指數爲中的節點數。

來源

2017-08-18 16:01:11 amit

啊，是的，我明白了，非常感謝您的幫助！我只是覺得這很奇怪，因爲我總是使用這種算法，而且我從來沒有遇到過時間問題。是因爲平均而言，執行時間與Dijkstra的執行時間相似嗎？謝謝你爲我做的一切！ – user8384788

@ user8384788我不知道它的平均時間複雜度是什麼，沒有計算它。如果你需要一個處理負權重的算法（無負循環），你應該更喜歡Bellman Ford算法。 – amit

啊，是的，沒錯。非常感謝您的幫助，我非常感謝！ – user8384788

Dijkstra的負權重算法（但沒有負循環）

回答

相關問題