9

所以我遇到了这个美丽的问题，它要求你编写一个程序来确定有向图中是否存在负无穷最短路径。（也可以认为是查找图中是否存在“负循环”）。这是问题的链接：

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 并检查它是否有效，但我很高兴能与您分享这个想法。

4

2 回答 2

18

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

该算法不适用于具有负循环的图的原因是此类图中的最短路径未定义：一旦进入负循环，您可以按照以下步骤将“最短路径”的成本尽可能低负循环多次。

负循环

考虑上面的例子：你从顶点 开始，并以 的成本Start到达。然后你用 的总成本去 ，用 的总成本去，现在你可以用 0 的总成本回到。通过扩展序列- - - - - - - - -...-您可以将路径的成本从to降低到尽可能小的负数。A1B-1C-4AStartABCABCABCFinishStartFinish

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

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

于 2013-11-21T14:11:39.413 回答
3

Dijkstra、Bellman-Ford 和 Floyd-Warshall 都没有算法可以处理负循环图，但后两者可以检测到一个，而 Dijkstra 不能，因为 Dijkstra 是贪婪的，而其他算法使用动态规划。此外，即使没有负循环，Dijkstra也不能使用负权重。

于 2013-11-21T16:34:48.960 回答