CODEWITHSUNDEEP
algorithmgraphgraph-theoryshortest-pathdijkstra
user8384788
user8384788

Reputation: 351

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

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

Upvotes: 1

Views: 1071

Answers (1)

amit
amit

Reputation: 178491

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.

Upvotes: 0

Related Questions