多元最短路-Floyd算法
2021/7/30 17:06:17
本文主要是介绍多元最短路-Floyd算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
时间限制:5.0s 内存限制:256.0MB
问题描述
给定\(n\)个结点两两之间的单向边的长度,求两两之间的最短路径。
输入格式
输入第一行包含一个整数\(n\),表示点数。
接下来\(n\)行,每行包含\(n\)个整数,第\(i\)行表示第\(i\)个点到每个点的边的长度,如果没有边,则用\(0\)表示。
输出格式
输出\(n\)行,第\(i\)行表示第\(i\)个点到其他点的最短路径长度,如果没有可达的路径,则输出\(-1\)。
样例输入
3 0 1 0 0 0 6 0 2 0
样例输出
0 1 7 -1 0 6 -1 2 0
数据规模和约定
\(1\leq n\leq 1000\),\(0<\)边长\(\leq 10000\)。
解析
Floyd 算法:
\(a_{ij} 表示\)i\(到\)j\(之间的边长,当\)i\(到\)j$之间没有变时取无限大.
\(f_{kij}\) 表示\(i\)到\(j\)允许使用节点\(1~k\)作为中间节点.
目标:\(f_{nij}\)
初值:\(f_{0ij} = a_{ij}\) 表示从\(i\)到\(j\)不允许经过其他节点作为中间节点,所以\(i\)到\(j\)的距离就是\(a_{ij}\)。
转移方程:$f_{kij} = min(f_{k-1ij}, f_{k-1ik} + f_{k-1kj})
不用k点作为中间节点 用
因为用三维数组内存超大,需要优化
优化:
可以压缩一个维度————k
可以使用滚动数组,只需f[2][n][n],大大减小了数组内存占用
于是f[k % 2][i][j] = min(f[(k - 1) % 2][i][j], f[(k - 1) % 2][i][k] + f[(k - 1) % 2][k][j])
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int INF = 1e9; int a[1005][1005]; int f[2][1005][1005]; int main(int argc, char** argv) { int n; cin >> n; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { cin >> a[i][j]; if (a[i][j] != 0) f[0][i][j] = a[i][j]; else if (i != j) f[0][i][j] = INF; } for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) f[k % 2][i][j] = min(f[(k - 1) % 2][i][j], f[(k - 1) % 2][i][k] + f[(k - 1) % 2][k][j]); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (f[n % 2][i][j] == INF) cout << -1 << " "; else cout << f[n % 2][i][j] << " "; } cout << endl; } return 0; }
这篇关于多元最短路-Floyd算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)