algorithm - 当我阅读 Djiktra 的算法时，负边会失败，但我实现了相同的概念并且我的代码正在运行？有什么错误吗？

Question

该代码也适用于负边缘，我使用了优先级队列
请检查它并让我知道它有什么问题以及为什么它甚至对负面影响也有效。约束:边的长度应小于10000
我在这里做错了什么吗？当我阅读 Djiktra 的算法时，负边会失败，但我实现了相同的概念并且我的代码正在运行？有什么错误吗？

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



    }

Answer 1

考虑这个例子:

无向图(6v,8e)

边缘(v1-v2(权重)):

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

现在，设源为 1 ，目标为 4 。从源到源 (1-3-6-1) 有一个循环，其权重为 (-7)。因此，让我们列出几条从源到目的地的路径以及权重:

• 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)

等那么，哪条路径最短呢？由于它是模棱两可的，所以该算法不起作用。现在，您可以争辩说，如果访问了一个节点，您将不会更新它。在这种情况下，您不会得到正确答案。可能在某些情况下，尽管有负边，算法会给出正确的结果，但这不是 Dijkstra 的工作方式。

理解 Dijkstra 的一个非常简单的方法是它在图上执行 BFS，从源到目的地，并在每一步中更新访问的节点。所以，如果有一个节点 n，它成本为 c 并且在 bfs 中深入几个级别，其成本变为 k (<c) 。然后，您将必须再次更新从 n 访问的所有节点以获得它们的较短路径(因为到 n 的路径现在更短)。由于图有负边，如果有环，n会无限更新，永远不会结束。