（数据结构）图的最短路径 弗洛依德算法(Floyd)

数据结构）图的最短路径 弗洛依德算法(Floyd)"/>

（数据结构）图的最短路径 弗洛依德算法(Floyd)

求解图的最短路径的另一种方法：迪杰斯特拉算法(Dijkstra)

求解图的最短路径的方法有两种，其中迪杰斯特拉算法(Dijkstra)适合求图中一个顶点到其他顶点的最短路径，而弗洛依德算法(Floyd)适合求图中每一对顶点之间的最短路径。 如果使用Dijkstra求解，则需要循环地以图中的每个顶点都作为起点，一共使用n次算法，时间复杂度为O(n ^ 3)。使用弗洛依德算法(Floyd)的时间复杂度也是O(n ^ 3 )，但是形式上比较简单。

算法思路

弗洛依德算法(Floyd) 使用的是动态规划的思想，我们首先我们使用一个二维数组dist[][]来存储当前的最短路径，然后寻找一个顶点k，如果vi到k的长度和k到vj的长度比vi到vj的长度还要低，就把dist[vi][vj]更新为dist[vi][k] + dist[k][vj]。

代码

以下面的有向图为例：

/*最短路径：弗洛依德算法
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1024;   //最大顶点数
int n,m;  //顶点的个数，边的个数
int dist[maxn][maxn];   //dist[i][j] 记录顶点i到顶点j的最短路径长度
int matrix[maxn][maxn];   //邻接矩阵/*
增加一条从v1指向v2的边，权值为k
*/
void link(int v1,int v2,int k){matrix[v1][v2] = k;//如果是无向图，则再加上matrix[v2][v1] = k;
}/*
图的初始化
*/
void init(){//初始化邻接矩阵for(int i = 0;i<=maxn;++i){for(int j = 0;j<maxn;++j){matrix[i][j] = -1;}}n = 4;m = 8;//下面m行建图link(1,2,1);link(1,4,4);link(2,3,9);link(2,4,2);link(3,1,3);link(3,2,5);link(3,4,8);link(4,3,6);
}/*
Floyd算法
*/
void floyd(){for(int i = 1;i <= n;++i){for(int j = 1;j<=n;++j){dist[i][j] = matrix[i][j];  //初始时，设置dist数组和matrix一样if(i == j){dist[i][j] = 0; //自己到自己的最短路径是0}}}for(int k = 1;k<=n;++k){for(int i = 1;i<=n;++i){for(int j = 1;j<=n;++j){if(dist[i][k] != -1/*i--k有计算过路径长度*/ && dist[k][j] != -1/*k--j有计算过路径长度*/ && (dist[i][k] + dist[k][j] < dist[i][j] || dist[i][j] == -1)/*新的路径长度比原来的小||原来没有计算过路径长度*/){dist[i][j] = dist[i][k] + dist[k][j];}}}}/*输出最短路径*/for(int i = 1;i<=n;++i){for(int j = 1;j<=n;++j){cout << i << " -- "<< j <<" : " << dist[i][j] << endl;}}
}int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);init();floyd();return 0;
}

运行结果