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,然后A以成本来到达1.那你去B与总成本-1,以C占总量的-4,现在你可以回去A为零的总成本.通过扩展序列Start- A- B- C- A- B- C- A- B- C-...- Finish你可以从减少路径的成本Start来Finish为你想尽可能小的负数.

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

当然可以修改Dijkstra算法来检测负循环,但这样做是没有意义的,因为你对没有负边缘有更强的限制.