欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Floyd 算法

程序员文章站 2022-04-06 14:05:17
...

众所周知,Floyd是来求最短路问题的算法

最短路径问题是图论研究中的一个经典算法问题, 指在寻找图(由结点和路径组成的)中两结点之间的最短路径。
例如:
Floyd 算法
Floyd是用了DP的思想
决策需要枚举中转点,不妨考虑也以中转点集为阶段
F[k,i,j]表示”可以经过标号≤k的点中转时”从i到j的最短路
F[0,i,j]=dis[i,j],dis为前面定义的邻接矩阵
F[k,i,j]=min{F[k-1,i,j] , F[k-1,i,k]+F[k-1,k,j]},O(N^3)
k这一维空间可以省略,变成F[i,j]
就成为了我们平时常见的Floyd算法
由于k是DP的阶段循环,所以k循环必须要放在最外层
Floyd 算法


例题:

Floyd 算法

样例

样例输入

5  7
1 2 10
1 4 30
1 5 100
2 3 50
3 5 10
4 3 20
4 5 60
1 5

样例输出

60
1 4 3 5

这是一道板题,把Floyd套上就完事了

正解
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN = 505;
int dp[MAXN][MAXN], pr[MAXN][MAXN];
int s, t;
int n, m;
void Read() {
	int i, j;
	scanf("%d %d", &n, &m);
	for(i = 1; i <= m; i++) {
		int A, B, C;
		scanf("%d %d %d", &A, &B, &C);
		dp[A][B] = C;
		pr[A][B] = A;
	}
}
void Write(int x) {
	if(pr[s][x] == 0)
		return;
	Write(pr[s][x]);
	printf(" %d", x);
}
int main() {
	int i, j, k;
	memset(dp, 0x3f, sizeof(dp));
	Read();
	for(i = 1; i <= n; i++)
		dp[i][i] = 0;
	for(k = 1; k <= n; k++) {
		for(i = 1; i <= n; i++) {
			for(j = 1; j <= n; j++) {
				int t = dp[i][j];
				if(dp[i][k] + dp[k][j] < dp[i][j]) {
					dp[i][j] = dp[i][k] + dp[k][j];
					pr[i][j] = pr[k][j];
				}
			}
		}
	}
	scanf("%d %d", &s, &t);
	printf("%d\n%d", dp[s][t], s);
	Write(t);
	return 0;
}
相关标签: Floyd 图论