重做图论，看了一些网上此题的程序，发现不少问题，此题虽然是最最基础的bellman_ford，但用来加深理解还是可以的：
1）bellman_ford 究竟要relax多少次，当从1到n存在且存在1 -> 2, 2 -> 3 ...n-1 -> n这样的边时，从1开始relax，到n显然是需要n-1次的，而如果其中存在负环的话，若relax次数大于n-1，总是存在新的可以收缩的点，因此最科学的次数是先做n-1次，再做第n次：
如果n-1次relax前已经不存在，则可以认为提前结束
若果第n次relax时仍有可relax点，则有负环的存在
2）对于此题，如何控制初值，一个比较原始的想法是，枚举起点，这样的时间复杂度大约为O(n^4)，但是还是可以过...
而经过观察发现，假设有一个原点0，到所有点的距离都是0，那么我们只需要从这个原点出发去判断图中可能出现的负环，因此我们只需要置初值dis[1..n]全部为0（任意相同值均可），做一次bellman_ford即可，而有不少的程序默认从1出发，一个简单的例子：

4 2 1
2 3 3
3 4 1
4 2 8
YES

• Re:一点看法 (748) shark6625 2010-11-20 20:51:22