关于floyd-warshall算法

Question

都说floyd算法能计算出每一对顶点的最短路,即使是有向图或者带负权路也同样适用,不过我怎么觉得不能有负权路啊?
例如有两个顶点:1,2
1->2的权为-1
2->1的权为-10
这么说,从1到2的最短路就是-11
可是我写的floyd算出来就是-21
哪位高人能帮我写出能计算出-11的floyd啊~十分感激!

Answer 1

存在负权的图中没有最短路的概念。
比如你的例子：
1-->2 -1
2-->1 -10
然后我再由1-->2那就成了-22。在求最短路时，不管是多源最短路floyed，单源最短路SPFA，dijsktra这些算法的应用，有的是必须保证图中无负权，有的可以判断图中有无负权。

Answer 2

负权回路本来就没有最短路。。。因为可以绕着负环一直转下去。。。