Floyd算法(多源最短路)
求任意两点u,v之间的最短路径长度,时间复杂度是O(n^3),顶点数在200以内,邻接矩阵实现(方便)
Floyd算法描述:
枚举顶点k在1~n
以顶点k作为中介点,枚举所有顶点对i和j(i在1~n,j在1~n)
如果dis[i][k]+dis[k][j]<dis[i][j]成立
赋值 dis[i][k]+dis[k][j]=dis[i][j]
Floyd的核心代码:
void floyd(){
int i,j,k;
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(map[i][k]!=inf&&map[k][j]!=inf&&map[i][j]>map[i][k]+map[k][j])
map[i][j]=map[i][k]+map[k][j];
}
}
}
}