于是，我来到了这个美丽的问题，要求你写一个程序，找到负无穷大的最短路径是否有向图存在。 （也可以被认为是查找图中的一个负周期是否存在）。这里有一个链接的问题：
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算法两次通过启动图中的任何来源解决了这个问题。我第二次运行算法，我检查，如果一个节点可以放宽。如果是这样，则肯定是有负循环中的曲线图。下面是我的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 。然后你去 B 与 1 ，到 C中的总成本与总 -4 ，现在你可以回去 A 与总成本零。通过扩展序列Start-A-B-C-A-B-C-A-B-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一个无限循环的图表？
发布评论