算法竞赛备赛——【图论】求最短路径——Floyd算法

floyd算法

基于动态规划
应用：求多源最短路 时间复杂度：n^3
dijkstra：不能解决负边权
floyd：能解决负边权 不能解决负边权回路问题
求最短路径：dijkstra bfs floyd

思路

1.让任意两点之间的距离变短：引入中转点k
通过k来中转 i---->k---->j < i----->j

2.找状态：
n个点都可以做中转点的情况下，i到j之间的最短路径的长度是x
最终状态：dp[n][i][j]=x;
中间状态：dp[k][i][j]=x;经过前k个点（1~k）做中转点的情况下，i到j之间的最短路径的长度是x
初始状态：dp[0][i][j]=a[i][j];

3.找状态转移方程
经过前k个点（1~k）做中转点的情况下，i到j之间的最短路径的长度是？
中间状态：dp[k][i][j]=？
前k-1个状态已知，前k-1个点（1~k-1)做中转点的情况下，i到j之间的最短路径的长度
if(dp[k][i][j]>dp[k-1][i][k]+dp[k-1][k][j])
dp[k][i][j]=dp[k-1][i][k]+dp[k-1][k][j]
else
dp[k][i][j]=dp[k-1][i][j];

代码实现

#include<iostream> 
using namespace std;
#define inf 0x7fffffff
int n, m;
int a[105][105];//邻接矩阵存图
int dp[105][105][105];int main() {cin >> n >> m;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {a[i][j] = inf;if (i == j) {a[i][j] = 0;}}}int x, y, w;for (int i = 1; i <= m; i++) {cin >> x >> y >> w;a[x][y] = w;}//初始化dpfor (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {dp[0][i][j] = a[i][j];}}for (int k = 1; k <= n; k++) {//枚举中转点for (int i = 1; i <= n; i++) {//枚举起点、终点for (int j = 1; j <= n; j++) {dp[k][i][j] = min(dp[k - 1][i][j], dp[k - 1][i][k] + dp[k - 1][k][j]);}}}//输出for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {cout << dp[n][i][j] << " ";}}return 0;
}

降维

#include<iostream> 
using namespace std;
//降维 三维降为二维
#define inf 0x7fffffff
int n, m;
int a[105][105];//邻接矩阵存图
int dp[105][105]; int main() {cin >> n >> m;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {a[i][j] = inf;if (i == j) {a[i][j] = 0;}}}int x, y, w;for (int i = 1; i <= m; i++) {cin >> x >> y >> w;a[x][y] = w;}//初始化dpfor (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {dp[i][j] = a[i][j];}}//三重循环的顺序不能变换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]);}}}//输出for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {cout << dp[i][j] << " ";}}return 0;
}