无向图中的floyd算法

  • Post author:
  • Post category:其他


floyd算法适用于求两个点之间的最短路径.

第一步:初始化矩阵

如果点i与点j之间是相连的它们之间的距离为x,那么a[i][j]=x;

如果点i与点j之间是不相连的,那么a[i][j]=∞:

如果点i等于点j,那么a[i][j]=0;

第二部:更新点i到点j的最短路径

假如点i与点k连通且点k与点j连通,如果点i到点k的距离加上点k到点j的距离小于之前点i直接到点j的距离则更新点i到点j的距离为点i到点k的距离加上点k到点j的距离,即a[i][j]=min(a[i][j],a[i][k]+a[k][j])。

核心代码:

for (int k = 1; k <= n; k++)

for (int i = 1; i <= n; i++)

for (int j = 1; j <= n; j++)

a[i][j] = min(a[i][j], a[i][k] + a[k][j]);

时间复杂度O(n^3)

空间复杂度O(n^2)

但是该算法的时间复杂度较高所以不适合用于较多数据的计算。



版权声明:本文为weixin_56002720原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。