algorithm - Dijkstra 的单源最短路径算法能否检测图中的无限循环？

Question

所以我遇到了这个美丽的问题，它要求您编写一个程序，找出有向图中是否存在负无穷大最短路径。 (也可以认为是寻找图中是否存在“负循环”)。这是问题的链接:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=499

我通过从图中的任何源开始运行 Bellman Ford 算法两次成功解决了这个问题。第二次运行该算法时，我检查是否可以放宽节点。如果是这样，那么图中肯定存在负循环。下面是我的 C++ 代码:

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
    int test;
    cin>>test;

    for(int T=0; T<test; T++)
    {

        int node, E;

        cin>>node>>E; 

        int **edge= new int *[E];
        for(int i=0; i<E; i++)
        {
            edge[i]= new int [3];
            cin>>edge[i][0]>>edge[i][1]>>edge[i][2];
        }

        int *d= new int [node];

        bool possible=false;

        for(int i=0; i<node;i++)
        {
            d[i]= 999999999;
        }

        d[node-1]=0;

        for(int i=0; i<node-1; i++)
        {

            for(int j=0; j<E; j++)
            {
                if(d[edge[j][1]]>d[edge[j][0]]+edge[j][2])
                    d[edge[j][1]]=d[edge[j][0]]+edge[j][2];
            }
        }

        // time to judge!
        for(int i=0; i<node-1; i++)
        {

            for(int j=0; j<E; j++)
            {
                if(d[edge[j][1]]>d[edge[j][0]]+edge[j][2])
                {
                    possible=true;
                    break;
                }

            } 

            if(possible)
                break;

        }

        if(possible)
            cout<<"possible"<<endl;
        else
            cout<<"not possible"<<endl;

    }
}

曾经有个教授跟我说Dijkstra的最短路径算法找不到这样的负环，但是他没有证明。我实际上怀疑这种说法。

我的问题是，Dijktstra 的单源最短路径算法能否检测到负循环？

当然，我可以尝试 Dijkstra 并检查它是否有效，但我很高兴与您分享这个想法。

Answer 1

您误解了您的教授:他一定说过如果图中存在负 循环，Dijkstra 算法将不起作用。允许正循环。

该算法不适用于具有负环的图的原因是此类图中的最短路径是未定义的:一旦出现负环，您可以将“最短路径”的成本降低到您希望的最低通过多次跟随负循环。

考虑上面的示例:您从顶点 Start 开始，并以 1 的成本到达 A。然后你去B总费用为-1，到C总费用为-4，现在您可以返回到 A，总成本为零。通过扩展序列 Start-A-B-C-A-B-C-A-B-C-...-Finish 您可以将从 Start 到 Finish 的路径成本降低到您希望的最小负数。

请注意，负循环限制适用于在图中查找最短路径的所有算法。对 Dijkstra 算法的限制甚至更强:它禁止所有负边。

当然可以修改 Dijkstra 算法来检测负循环，但这样做没有意义，因为您有没有负边的更强限制。