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

Question

I believe that the implementation of Dijkstra's Algorithm below works for all graphs with negative weights but no cycles with a negative sum.

However, I have seen many people say that Dijkstra's doesn't work for graphs with negative weights, so I am believing that either the algorithm is wrong or the execution time is far slower than Dijkstra's Algorithm.

I was just wondering if someone could please help me with this code? Thank you very much for all your help!

(Edit: This question is different from others since I am also wondering if the execution time of this algorithm is far longer than Dijkstra's Algorithm since nodes may be visited multiple times)

#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);
            }
        }
    }
}

Possible duplicate of [Negative weights using Dijkstra's Algorithm](https://stackoverflow.com/questions/6799172/negative-weights-using-dijkstras-algorithm) — BlueRaja - Danny Pflughoeft, Aug 18 '17 at 15:40
Possibly, but in the graph from the first answer, this algorithm gives the correct weight (-200). Also, I am wondering if possibly this algorithm, since it visits each node multiple times, takes much longer to execute than Dijkstra's. — user8384788, Aug 18 '17 at 15:51
It's correct, but it's exponential in the worst case. I don't remember how to build an example of such a graph, though. — kraskevich, Aug 18 '17 at 15:56
@user8384788 Please read https://stackoverflow.com/a/25158544/238419 — BlueRaja - Danny Pflughoeft, Aug 18 '17 at 16:13
Oh whoops. But I am still wondering if the exponential case is common, since I have never run into this issue before when using this algorithm. Thanks! — user8384788, Aug 18 '17 at 16:16

score 0 · Accepted Answer · answered Aug 18 '17 at 16:01

0

Even if correct (didn't prove it, but it seems to be), your algorithm suffers from bad time complexity.

Specifically, if you look at a complete DAG:

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

And for simplicity of the example we assume the algorithm traverses edges in reverse order ((u,v) before (u,x) if x < v) (Note that this is just for simplification, and even without it you can build a counter example by reversing the directions of the edges).

Note that your algorithm reopens each edge every time it opens it. That means you traverse all paths in this graph, which is exponential in the number of nodes.

answered Aug 18 '17 at 16:01

amit

175,853
27
231
333

Ah yes, I see that, thank you so much for all your help! I just feel it is weird since I always use this algorithm and I have never run into a time problem with it. Is it because on average, the execution time is similar to Dijkstra's execution time? Thank you for everything! – user8384788 Aug 18 '17 at 16:14
@user8384788 I have no idea what's the average time complexity of it, didn't calculate it. If you need an algorithm that handles negative weights (w/o negative loops), you should prefer Bellman Ford algorithm though. – amit Aug 18 '17 at 16:52
Ah yes, right. Thank you very much for all your help, I really appreciate it! – user8384788 Aug 18 '17 at 17:47

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

1 Answers1