Dijkstra的“单源最短路径”算法可以检测图中的无限循环吗？

问题描述

因此，我遇到了一个漂亮的问题，要求您编写一个程序，以查找有向图中是否存在负无穷最短路径。 （也可以认为是在图中找到负周期）。这是问题的链接：

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:

我通过从图中的任何源开始两次运行Bellman Ford Algorithm成功解决了该问题。第二次运行算法时，我检查节点是否可以放宽。如果是这样，则图中肯定有一个负周期。以下是我的C ++代码：

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's并检查它是否可以工作，但是我很高兴与您分享这个想法。

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.

考虑上面的示例：您从顶点开始开始，并以 1 的价格到达 A 。然后转到总成本为 -1 的 B ， C ，总计为 -4 ，现在您可以返回到 A ，而总费用为零。通过扩展序列开始- A - B - C - A - B - C - A - B - C -...- 完成，您可以将路径成本从开始减少到完成尽可能地减小负数。

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的“单源最短路径”算法可以检测图中的无限循环吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！