Floyd算法：
1、基本思想
求解所有点的路径需要进行n次试探。对于顶点i到顶点j的路径长度，首先考虑让路径经过顶点1，比较路径（i，j）和（i，1，j）的长度取其短者为当前求得的最短路径长度。
Floyd算法的本质是动态规划。递归方程如下：
dp[i]j][k]=min{dp[i][j][k-1],dp[i][k][k]+dp[k][j][k]}
特殊的有：
当k=0时，dp[i][j][0]=w(i,j)，其中dp[i][j][k]表示从i到j经过k的最短路径。
2、样例代码
//Floyd
viod Floyd() {
for(iint i=0; i<sz; i++) {
for(int j=0; j<sz; j++) {
int i_distances[j][i]+distances[i][k];
if(distances[j][k]>t_dis)
distances[j][k]=t_dis;
}
}
}
3、注意事项
Floyd可以处理负权边，但无法处理负环。
Floyd算法适用于无向图，有向图，此时一个无向边次相当于两个有向边。
求出全源最短路径的计算复杂度为O（n3）。
网友评论