跪求 弗洛伊德算法 一个错误的解释：

floyd算法用以解决所有点对最短路径。

floyd算法基本思想是递推，动态规划。我们记 dp[j][k] 表示图中顶点 i 到 j 的最短路径，且该最短路径中，所经过的中间顶点(不包括 i, j) 的范围为 [1,k]，由此我们可以得到以下递推式：

dp[j][k]= w[j] 如果 k== 0

dp[j][k]= min{ dp[k][k-1]+ dp[k][j][k-1] } 如果 k>= 1。

实际中，空间上我们可以减少一维。

floyd算法同样可以来解决一些其它问题

1) 有向图的最小(或最大)环

这个问题答案其实就是自身到自身的最短路径，运行完 floyd 后，对每个顶点取自身到自身距离的最小者。

2) 无向图的最小环

根据以上的递推式，dp[j][k] 表示 i 到 j 的最短路径，且该最短路径中，所经过的中间顶点(不包括 i, j) 的范围为 [1,k]。

此时我们可以枚举出顶点序列最大为 k+ 1 的所有最小环，如何枚举：设与顶点序列最大的顶点 k+ 1 相连的两个顶点为 x, y，x,y 须满足 x, y<= k。这样最小环构成为 边 边 及 x 到 y 的最短路径。

Poj 1734 Sightseeing trip

#include
#include

int const N= 110, inf= 5000000;
int mat[N][N], dist[N][N], pre[N][N], path[N], n, m, top= 0, p;

#define min(a,b) ((a)<(b)?(a):(b))

int main(){
scanf("%d%d",&n,&m );
for( int i= 0; i<= n; ++i )
for( int j= 0; j<= n; ++j ){
mat[j]= inf; dist[j]= inf; pre[j]= j; }
while( m-- ){
int u, v, d;
scanf("%d%d%d",&u,&v,&d);
mat[v]= min( mat[v], d );
mat[v]= mat[v];
dist[v]= mat[v]; dist[v]= mat[v];
}
int ans= inf;
for( int k= 1; k<= n; ++k ){
for( int x= 1; x< k; ++x )
for( int y= 1; y< x; ++y ){
if( mat[x][k]+ mat[k][y]+ dist[x][y]< ans ){
ans= mat[x][k]+ mat[k][y]+ dist[x][y];
top= 0; path[top++]= k; p= x;
while( p!= y ){
path[top++]= p; p= pre[p][y];
}
path[top++]= y;
}
}
for( int i= 1; i<= n; ++i )
for( int j= 1; j<= n; ++j )
if( dist[k]+ dist[k][j]< dist[j] ){
dist[j]= dist[k]+ dist[k][j];
pre[j]= pre[k]; }
}
if( top> 0 ){
printf("%d", path[0] );
for( int i= 1; i< top; ++i ) printf(" %d", path );
puts("");
}else puts("No solution.");

return 0;
}