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的负权重算法（但没有负循环）

回答

相关问题