Floyd-Warshall算法使用DP方法来求解任意两点间的最短路问题。
i到j的最短路分正好经过顶点k一次和完全不经过顶点k两种情况来讨论。不断的进行d[i][j] = min(d[i][j], d[i][k] + d[k][j])的更新来实现，复杂度是O(n ^ 3)。
此算法可以处理负权边，也可以判断图中是否有负圈，只需检查是否存在d[i][i]是负数的顶点i就可以了。
//Floyd-Warshall
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int
MAXV = 105, MAXE = 10005, INF = 0x3f3f3f3f;
int v, e;
int d[MAXV][MAXV];
bool Floyd_Warshall() {
for(int k = 1; k <= v; ++k) {
for(int i = 1; i <=v; ++i) {
for(int j = 1; j<= v; ++j) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
for(int i = 1; i <= v; ++i)
if(d[i][i] < 0)
return false;
return true;
}
int main() {
while(scanf("%d%d", &v, &e) != EOF && v && e) {
for(int i = 1; i <= v; ++i) {
for(int j = 1; j <= v; ++j) {
d[i][j] = d[j][i] = (i == j ? 0 : INF);
}
}
for(int i = 1; i <= e; ++i) {
int f, t, c;
scanf("%d%d%d",&f, &t, &c);
d[f][t] = d[t][f] = c;
}
if(Floyd_Warshall())
printf("%d\n", d[1][v]);
else
printf("有负圈\n");
}
return 0;
}
