可以Dijkstra的单源最短路径算法dectect一个无限循环的图表？ [英] Can Dijkstra's Single Source Shortest Path Algorithm dectect an infinite cycle in a graph?

问题描述

于是，我来到了这个美丽的问题，要求你写一个程序，找到负无穷大的最短路径是否有向图存在。 （也可以被认为是查找图中的一个负周期是否存在）。这里有一个链接的问题：

So I came to this beautiful problem that asks you to write a program that finds whether a negative infinity shortest path exists in a directed graph. (Also can be thought of as finding whether a "negative cycle" exists in the graph). Here's a link for the problem:

<一个href="http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=499" rel="nofollow">http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=499

余成功运行的Bellman Ford算法​​两次通过启动图中的任何来源解决了这个问题。我第二次运行算法，我检查，如果一个节点可以放宽。如果是这样，则肯定是有负循环中的曲线图。下面是我的C ++ code：

I successfully solved the problem by running Bellman Ford Algorithm twice by starting with any source in the graph. The second time I run the algorithm, I check if a node can be relaxed. If so, then there is definitely a negative cycle in the graph. Below is my C++ code:

#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的最短路径算法无法找到这样的负循环，但他并没有证明它。其实，我怀疑这种说法。

A professor told me once that Dijkstra's shortest path algorithm cannot find such negative cycle, but he did not justify it. I actually doubt this claim.

我的问题是，可以Dijktstra的单源最短路径算法检测不良的循环？

My question is, can Dijktstra's single source shortest path algorithm detect that negative cycle?

当然，我可以尝试Dijkstra的，并检查它是否会工作，但我很高兴能与大家分享了这个想法。

Of course, I can try Dijkstra's and check whether it will work, but I was excited to share this idea with you.

推荐答案

您误解了你的教授：他肯定说，Dijkstra算法是行不通的，如果有一个负周期图表中。正循环是允许的。

You misunderstood your professor: he must have said that Dijkstra's algorithm will not work if there is a negative cycle in the graph. Positive cycles are allowed.

算法不会在图形上负循环工作的原因是，在这样的图的最短路径是不确定的：一旦你得到一个负循环，你可以把你的最短路径的，你想低的成本通过多次如下负周期

The reason the algorithm will not work on graphs with negative cycles is that the shortest path in such graphs is undefined: once you get to a negative cycle, you can bring the cost of your "shortest path" as low as you wish by following the negative cycle multiple times.

考虑一下上面的例子：你开始在顶点启动，到达 A 与成本 1 。然后你去<$​​ C $ C> B 与 1 ，到 C中的总成本与总 -4 ，现在你可以回去 A 与总成本零。通过扩展序列<$c$c>Start-<$c$c>A-<$c$c>B-<$c$c>C-<$c$c>A-<$c$c>B-<$c$c>C-<$c$c>A-<$c$c>B-<$c$c>C-...-<$c$c>Finish你可以从启动到完成如你所愿降低路径的成本尽可能小的负数。

Consider the example above: you start at the vertex Start, and arrive at A with the cost of 1. Then you go to B with the total cost of -1, to C with the total of -4, and now you can go back to A with the total cost of zero. By extending the sequence Start-A-B-C-A-B-C-A-B-C-...-Finish you could reduce the cost of a path from Start to Finish to as small a negative number as you wish.

需要注意的是负周期限制适用于所有的算法寻找最短路径图。在Dijkstra算法的限制是更强大：它禁止所有负面的边缘

Note that the negative cycle restriction applies to all algorithms for finding shortest path in a graph. The restriction on Dijkstra's algorithm is even stronger: it prohibits all negative edges.

这当然是可以修改的Dijkstra算法来检测负循环，但没有一点这样做，因为你有没有负面的边缘更为强烈的约束。

It is certainly possible to modify Dijkstra's algorithm to detect negative cycles, but there is no point in doing so, because you have a stronger restriction of having no negative edges.

这篇关于可以Dijkstra的单源最短路径算法dectect一个无限循环的图表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！