1

The code works for negative edges too and I have used priority queue
please check it and let me know what's wrong with it and why is this working even for negative edges. Constraint: edges should be less than 10000 length
Am I doing something wrong here? As I read Djiktra's algo fails for negative edges but I implemented the same concept and my code is working? Is there some bug?

#include<iostream>
    #include<queue>
    using namespace std;

    struct reach
    {
        int n;
        int weight;
    };

    struct cmp
    {
        bool operator()(reach a, reach b)
        {
            return a.weight>b.weight;
        }
    };

    class sp
    {
        int *dist;
        int n;
        int **graph;
        int src;
        public:
            sp(int y)
            {
                n=y;
                src=1;
                dist=new int[n+1];
                graph=new int*[n+1];
                for(int i=0;i<=n;i++)
                {
                    graph[i]=new int[n+1];
                }
                for(int i=2;i<=n;i++)
                {
                    dist[i]=10000;
                }
            //  cout<<INT_MAX<<endl;
                dist[src]=0;
                for(int i=1;i<=n;i++)
                {
                    for(int j=1;j<=n;j++)
                    {
                        graph[i][j]=10000;
                    }
                }
                graph[1][1]=0;
            }
            void read()
            {
                int a;
                cout<<"enter number of edges"<<endl;
                cin>>a;
                cout<<"now enter the two vertices which has an edge followed by the weight of the edge"<<endl;
                while(a--)
                    {//cout<<"location: "<<i<<" : "<<j<<endl;
                    int as, ad,val;
                    cin>>as>>ad>>val;


                            graph[as][ad]=val;

                    }

            }
            void finder()
            {cout<<"enetered"<<endl;
                priority_queue<reach, vector<reach>, cmp> q;
                for(int i=1;i<=n;i++)
                {
                    if(dist[src]+graph[src][i]<dist[i])
                    {
                        reach temp;
                        temp.n=i;
                        cout<<i<<endl;
                        temp.weight=graph[src][i];
                        q.push(temp);
                        dist[i]=graph[src][i]+dist[src];
                    }
                }
                    while(q.empty()!=1)
                    {
                        reach now =q.top();
                        //cout<<" we have here: "<<now.n<<endl;
                        q.pop();
                        for(int i=1;i<=n;i++)
                        {
                            if((dist[now.n] + graph[now.n][i])<dist[i])
                            {
                                dist[i]=dist[now.n]+graph[now.n][i];
                                cout<<"it is: "<<i<<" : "<<dist[i]<<endl;

                                reach temp;
                                temp.n=i;
                                //cout<<temp.n<<endl;
                                temp.weight=graph[now.n][i];
                                q.push(temp);
                            }
                        }


                    }
                }

            void print()
            {
                for(int i=1;i<=n;i++)
                {
                    cout<<"we have: "<<dist[i]<<" at "<<i;
                    cout<<endl;
                }

                cout<<endl;
            }

        };


        int main()
        {cout<<"enter no. of vertices"<<endl;
            int n;
            cin>>n;
            sp sp(n);
            sp.read();
            sp.finder();
            sp.print();



    }
chareon
  • 120
  • 13
Robert
  • 19
  • 2
  • You may find that it works in some cases, but doesn't work in general. – Vaughn Cato Oct 01 '15 at 06:04
  • http://stackoverflow.com/questions/6799172/negative-weights-using-dijkstras-algorithm http://stackoverflow.com/questions/13159337/why-doesnt-dijkstras-algorithm-work-for-negative-weight-edges – sve Oct 01 '15 at 06:40

2 Answers2

2

Consider this example:

Undirected Graph(6v,8e)

Edges (v1-v2 (weight)):

  • 1-2 (2)
  • 2-3 (1)
  • 1-3 (-2)
  • 1-6 (-2)
  • 3-6 (-3)
  • 5-6 (1)
  • 4-5 (2)
  • 2-5 (1)

Now, Let source be 1 and destination be 4. There is one cycle from source to source (1-3-6-1) which weighs (-7). So, lets list a few paths from source to destination with weights:

  • 1-6-5-4 (1)
  • 1-3-6-5-4 (-2)
  • 1-3-6-1-3-6-5-4 (-9)
  • 1-3-6-1-3-6-1-3-6-5-4 (-16)

etc. So, which path is the shortest? Since it is ambiguous, the algorithm does not work. Now, you can argue that if a node is visited, you will not update it. In this case, you will not get the correct answer. May be there are some cases where in-spite of having negative edges, algo gives correct results, but this is not how Dijkstra works.

A really simple way to understand Dijkstra is that it performs BFS on the graph, from source till destination, and in every step it updates the visited nodes. So, if there is a node n which has cost c and a few levels deep in bfs, its cost becomes k (<c). Then again you will have to update all the nodes visited from n for their shorter paths (because path to n is now shorter). Since graph has negative edges, if it has a cycle, n will keep updating infinitely and will never end.

vish4071
  • 5,135
  • 4
  • 35
  • 65
1

The simplest graph for which Dijkstra's algorithm fails with negative weights has adjacency matrix

0 1  2
1 0 -3
2 -3 0

and looks for a route from vertex 0 to vertex 1. The first vertex to come off the priority queue is vertex 1 at distance 1, so that's the route returned. But there was a route of total weight -1 via a vertex which is still in the priority queue, with weight 2.

Peter Taylor
  • 4,918
  • 1
  • 34
  • 59