求负权最短路径 除了Bellman - Ford算法，有没有另一种算法可以判断出负开销回路的存在
因为Bellman - Ford只能求无负权回路的图的最短路径
我想找一种既可以计算出定点的非负无穷的最短路径长度，又可以报告出负开销回路的存在。
最好既有思想又有代码：）
谢谢！
问题点数：100、回复次数：11Top
1 楼mostideal（三甲）回复于 2005-06-05 17:31:14 得分 0
mark!! 学习。。Top
2 楼qhfu（改个名字）回复于 2005-06-05 18:05:11 得分 50
floyd算法 满足吗？
通过三个 for 循环，根据三角形定理。
伪代码：
w = n*n;// w为n*n阶 矩阵， n为图的顶点数 。
D(0) = w;
for(int k = 0;k<n;k++)
for(int j=0;j<n;j++)
for(int i =0;i<n;i++)
d(i,j)(k) = min(d(i,j)(k-1),d(i,k)(k-1)+d(j,k)(k-1));
return D(n);
// d(i,j)(k)表示矩阵D(k)的第i行，j列。
Top
3 楼zdwang99（芳心）回复于 2005-06-05 23:30:46 得分 0
floyd算法也只能求没有负回路的情况
并不能判断出负回路的存在阿
不过还是谢谢Top
4 楼nasi00（莫傲·逍遥）回复于 2005-06-06 02:29:26 得分 50
bellman-ford可以判断负回路阿
你的意思是不是既要判断负回路，又要找到那些两点间的路径没有负回路的最短距离呢？Top
5 楼zdwang99（芳心）回复于 2005-06-06 23:27:20 得分 0
是的
据我所知，有方法可以使复杂度控制在O(n*e)
可是不知道算法的具体思想Top
6 楼nasi00（莫傲·逍遥）回复于 2005-06-07 03:53:29 得分 0
没研究过，不知道可不可以采用这种思想（猜测阿 ^_^）：找到负回路，然后去掉，再求最短路径Top
7 楼zdwang99（芳心）回复于 2005-06-07 14:13:40 得分 0
呵呵，要是发现有负回路，就可以终止算法了，就不用继续求喽
不过还是谢谢你：）
Top
8 楼nasi00（莫傲·逍遥）回复于 2005-06-09 03:27:10 得分 0
你不是说要发现负回路，还要求出没有负回路经过的点的最短路径么？
那你可以在发现负回路以后把这条路径上的点统统去掉阿，原理上行得通的……，不过这样也有些问题，因为去掉这些点就改变了图的结构了，很可能会去掉一些影响结果的边 -_-#Top
9 楼zdwang99（芳心）回复于 2005-06-11 10:36:28 得分 0
呵呵，你真好
顺便问你一下，如果图中有负边，但是没有负回路，不知道Djistra算法能不能用啊？
Top
10 楼qhfu（改个名字）回复于 2005-06-11 19:53:49 得分 0
Djistra算法对于有负边的图是不能用的Top
11 楼nasi00（莫傲·逍遥）回复于 2005-06-14 18:53:03 得分 0
负边用不了Dijkstra的，这个是一定的咯 ^_^Top
