初始化
从row到col的距离,row为行数,col为列数
例如:2到3的距离=3
以 1 为中介点
3到2=max > 3到1=7 + 1到2=2,所以更新为9
4到2=max > 4到1=5 + 1到2=2,所以更新为7
4到3=12 > 4到1=5 + 1到3=6,所以更新为11
以 2 为中介点
1到3=6 > 1到2=2 + 2到3=3,所以更新为5
4到3=11 > 4到2=7 + 2到3=3,所以更新为10
以 3 为中介点
2到1=max > 2到3=3 + 3到1=7,所以更新为10
2到4=max > 2到3=3 + 3到4=1,所以更新为4
以 4 为中介点
2到1=10 > 2到4=4 + 4到1=5,所以更新为9
3到1=7 > 3到4=1 + 4到1=5,所以更新为6
3到2=9 > 3到4=1 + 4到2=7,所以更新为8
时间复杂度:O(n*n*n)
核心代码:
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(e[i][j]>e[i][k]+e[k][j])
e[i][j]=e[i][k]+e[k][j];