图论：Floyd算法

我们在之前介绍的一些图论中的最短路算法，像一些dijkstra朴素版、dijkstra堆优化、Bellman算法、Bellman队列优化（SPFA）等等，都是针对于单源问题求最短路，而对于多源问题，就需要用到今天介绍的Floyd算法了。顾名思义多源，就是有多个源头，即有多个出发点，也就是说会在q次询问中查询多个起点到任意一点的最短路径，而前面介绍的单源最短路的一些算法只能查询一个起点到所有节点的最短路。

• Floyd 算法对边的权值正负没有要求，都可以处理。

Floyd算法核心思想是动态规划。

首先来复习一些动态规划五部曲：

• 确定dp数组以及下标的含义
• 确定递推公式
• dp数组如何初始化
• 确定遍历顺序
• 举例推导dp数组

其中，最终要的就是第二部的确定递推公式了（即状态转移方程）

我们将三维数组dp[i][j][k]来表示为节点i到节点j以[1...k]集合中的一个节点为中间节点的最短距离。

那么我们要想从节点i到节点j，那么我们就可以分为两种情况：

• 节点i到节点j的最短路中经过节点k
• 节点i到节点j的最短路中不经过节点k

首先对经过节点k进行分析，我们是想从i到j，然后经过节点k，那么我们是不是就是分为了两段路径，一是从i到了节点k，然后二再从节点k到节点j，那么这种情况的状态转移方程就为：

dp[i][j][k] = dp[i][k][k-1] + dp[k][j][k-1]

为什么这里的第三维是k-1呢，因为我们是在这里经过节点k的，所以我们不能包含节点k，这个节点k是当前走的选择！

然后我们分析第二种情况，这种情况就比较简单了，我们要不经过节点k，那么状态转移方程就直接为：

dp[i][j][k] = dp[i][j][k-1]

所以我们只需要对这两种情况去最小值min即可！

接下来的就是dp数组的初始化解题了，我们现在是三维数组，节点是从1-n，所以0是无意义的，所以我们直接用k = 0来表示初始一个点都不经过的状态，那么此时的初始化操作就完成了，这时候我们对三维数组的底面（i和j构成的平面）已经完成了初始化，那么我们就需要从下一层一层往上递推了，不断地枚举k的大小，所以对k的枚举应该在最外层！！！（这里是核心）。

具体的初始化部分可以通过以下操作来完成：

for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;dp[u][v][0] = w;dp[v][u][0] = w;//双向图}

此外所有的初始化都为inf即可（因为求的是最小距离）

之后就是递推过程了：

for(int k=1;k<=n;k++)//k在最外层！
{for(int i=1;i<=n;i++){for(int j=1;j<=n;j++) dp[i][j][k] = min(dp[i][k][k-1] + dp[k][j][k-1],dp[i][j][k-1]);}
}

最后的查询操作就直接可以通过o(1)的时间复杂度来完成：

cout<<dp[start][end][n]<<endl;

题目链接：小明逛公园

这道题也就是经典的Floyd算法的板子题，代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define endkl endl;
inline int lowbit(int x)
{return x & (-x);
} 
const int INF = 0x3f3f3f3f;
const int inf = 1e18; int n,m;
// void Floyd()
// {// for(int k=1;k<=n;k++)// {// for(int i=1;i<=n;i++)// {// for(int j=1;j<=n;j++) dp[i][j][k] = min(dp[i][k][k-1] + dp[k][j][k-1],dp[i][j][k-1]);// }// }
// }
void solve()
{cin>>n>>m;vector<vector<vector<int>>> dp(n+1,vector<vector<int>>(n+1,vector<int>(n+1,inf)));for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;dp[u][v][0] = w;dp[v][u][0] = w;}// Floyd();for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++) dp[i][j][k] = min(dp[i][k][k-1] + dp[k][j][k-1],dp[i][j][k-1]);}}int t;cin>>t;while(t--){int start,end;cin>>start>>end;if(dp[start][end][n] == inf) cout<<"-1"<<endl;elsecout<<dp[start][end][n]<<endl;}
//  cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;
//  cin>>T;while(T--) solve(); return 0;
} 

当然我们可以对空间进行压缩，使其变为二维数组：

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define endkl endl;
inline int lowbit(int x)
{return x & (-x);
} 
const int INF = 0x3f3f3f3f;
const int inf = 1e18; int n,m;
// void Floyd()
// {// for(int k=1;k<=n;k++)// {// for(int i=1;i<=n;i++)// {// for(int j=1;j<=n;j++) dp[i][j][k] = min(dp[i][k][k-1] + dp[k][j][k-1],dp[i][j][k-1]);// }// }
// }
void solve()
{cin>>n>>m;// vector<vector<vector<int>>> dp(n+1,vector<vector<int>>(n+1,vector<int>(n+1,inf)));vector<vector<int>> dp(n+1,vector<int> (n+1,inf));for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;// dp[u][v][0] = w;// dp[v][u][0] = w;dp[u][v] = w;dp[v][u] = w;}// Floyd();for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++) dp[i][j] = min(dp[i][k] + dp[k][j],dp[i][j]);// dp[i][j][k] = min(dp[i][k][k-1] + dp[k][j][k-1],dp[i][j][k-1]);}}int t;cin>>t;while(t--){int start,end;cin>>start>>end;// if(dp[start][end][n] == inf) cout<<"-1"<<endl;// else// cout<<dp[start][end][n]<<endl;if(dp[start][end] == inf) cout<<"-1"<<endl;else cout<<dp[start][end]<<endl;}
//  cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;
//  cin>>T;while(T--) solve(); return 0;
} 

下面是一道洛谷上的一个Floyd算法的模板题：

B3647 【模板】Floyd - 洛谷

大家可以作为练习题巩固一下。

• 时间复杂度：O(n ^ 3)
• 空间复杂度：O(n ^ 2)

时间复杂度还是不乐观的，所以在竞赛中，如果源点较少的话，可以优先考虑用多次的Dijkstra跑出结果！

下面附上Floyd算法的XCPC模板，有需要的可拿：

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define endkl endl;
inline int lowbit(int x)
{return x & (-x);
} 
const int INF = 0x3f3f3f3f;
const int inf = 1e18;void floyd_solve()
{int n, m;cin >> n >> m;// 初始化邻接矩阵vector<vector<int>> dp(n+1, vector<int>(n+1, inf));for(int i = 1; i <= n; i++) dp[i][i] = 0;  // 自环距离为0// 读入边for(int i = 1; i <= m; i++){int u, v, w;cin >> u >> v >> w;dp[u][v] = min(dp[u][v], w);  // 处理重边dp[v][u] = min(dp[v][u], w);  // 无向图}// Floyd核心算法for(int k = 1; k <= n; k++){for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);}}}// 查询处理int q;cin >> q;while(q--){int u, v;cin >> u >> v;if(dp[u][v] == inf) cout << "-1" << endl;else cout << dp[u][v] << endl;}
}signed main()
{IOSint T = 1;// cin >> T;while(T--) floyd_solve();return 0;
}