刚开始学最短路，想提一个问题：
根据算法导论上的说法，对源点s调用Bellman-Ford算法，此算法返回值对应于“从源点s可达的顶点”中是否存在负权回路。

但这并不能说明整张图中有没有负权回路！！！

我自己写的代码，还有网上见到的很多代码都是直接对顶点1调用此算法，然后输出相应结果。但根据上面的分析，这样的算法的漏洞是很明显的。
比如下面一组数据（感谢Firefrog）：

1
4 1 3
1 4 200
2 1 1
2 3 1
3 2 1

答案应该是YES

这组数据中，顶点1不存在可达的负权回路，但别的顶点（2->3->2……）却可以形成负权回路。

当然可以对每个顶点都调用一次Bellman-Ford算法，但时间复杂度会达到（V^4），显然TLE；（我只对顶点1调用已经800~1000ms了）
一个优化的想法是对源点1不可达的顶点调用此算法，但最差情况下复杂度还是不会改变。


所以如果非要用Bellman-Ford算法该怎么做呢？？虚心请教各位大牛。

• 你这复杂度是闹哪样... (359) braveTester 2012-03-22 19:31:35
  • Re:你这复杂度是闹哪样... (350) Ruby931031 2012-03-22 23:04:05
    • Re:你这复杂度是闹哪样... (407) braveTester 2012-03-22 23:39:51
      • Re:你这复杂度是闹哪样... (51) jwpan 2012-07-19 23:20:53
• 半年之后再看这道题，感觉果然不一样…… (1666) Ruby931031 2012-07-12 00:41:09
• SPFA果然很嚣张。。 (2071) Ruby931031 2012-07-12 01:37:16