Dijkstra 的负权重算法（但没有负循环）

Question

我相信下面的 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);
            }
        }
    }
}

Answer 1

即使正确（没有证明，但似乎是），你的算法时间复杂度很差。

具体来说，如果您查看完整的 DAG：

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

为了示例的简单起见，我们假设算法以相反的顺序遍历边（(u,v) 在 (u,x) 之前，如果 x < v）（请注意，这只是为了简化，甚至没有它，你可以通过反转边的方向来构建一个反例。

请注意，您的算法每次打开每条边时都会重新打开它。这意味着你遍历了这个图中的所有路径，节点数呈指数级。

Dijkstra 的负权重算法（但没有负循环）

Dijkstra's Algorithm With Negative Weights (But No Negative Cycles)

algorithm

graph-theory

graph

dijkstra

shortest-path