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

本文介绍了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:

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

我通过从图中的任何源开始两次运行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.