3.2最短路之全源最短路(Floyd)
这个算法用于求所有点对的最短距离。比调用n次SPFA的优点在于代码简单,时间复杂度为O(n^3)。【无法计算含有负环的图】
依次扫描每一点(k),并以该点作为中介点,计算出通过k点的其他任意两点(i,j)的最短距离,这就是floyd算法的精髓!同时也解释了为什么k点这个中介点要放在最外层循环。
void floyd() { memset(dis,,sizeof(dis)); ;i<=n;i++) dis[i][i]=; ;k<=n;k++)//中介点 ;i<=n;i++) ;j<=n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); }