首页 / 算法 / 弗洛伊德算法(Floyd)求最短路径
弗洛伊德算法(Floyd)求最短路径
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了弗洛伊德算法(Floyd)求最短路径,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1506字,纯文字阅读大概需要3分钟。
内容图文
![弗洛伊德算法(Floyd)求最短路径](/upload/InfoBanner/zyjiaocheng/829/c3e671e25ccc445c8176412f5f6443a4.jpg)
弗洛伊德算法
图来源于百度百科:Floyd算法
其时间复杂度为:O(n^3),(这时间复杂度,分分钟TLE。。。。。)
//#include<bits/stdc++.h>
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<stack>
#include<string.h>
#include<math.h>
#include<stack>
using namespace std ;
typedef long long ll;
#define MAXN 10005
#define INF 0x3f3f3f3f
#define MALL (BiTnode *)malloc(sizeof(BiTnode));
int path[MAXN][MAXN]; //最短路径上顶点vj的前一项的序号
int D[MAXN][MAXN]; //vi到vj的最短路径
void init(int n)
{
for(int i=0; i<n; ++i)
for(int j=0; j<n; ++j)
D[i][j] = INF;
}
void PATH(int n)
{
for(int i=0; i<n; ++i)
for(int j=0; j<n; ++j)
if(D[i][j] < INF && i!=j)
path[i][j] = i;
else
path[i][j] = -1;
}
void floyd(int n) //floyd算法
{
for(int k=0; k<n; ++k)
for(int i=0; i<n; ++i)
for(int j=0; j<n; ++j)
if(D[i][k] + D[k][j] < D[i][j])
{
D[i][j] = D[i][k] + D[k][j];
path[i][j] = path[k][j]; //更新j的前驱为k
}
}
int main()
{
cout << "请输入顶点的个数和边的关系数" << '\n';
int n, m; //n个顶点和m条边关系
cin >> n >> m;
init(n);
cout << "\n请依次输入各组边的关系" << '\n';
for(int i=0; i<m; ++i)
{
int u, v, len;
cin >> u >> v >> len;
D[u][v] = len;
}
PATH(n);
floyd(n);
cout << "\n用弗洛伊德算法计算后整个矩阵的最短路径为:" << '\n';
for(int i=0; i<n; ++i)
{
for(int j=0; j<n; ++j)
{
if(D[i][j] < INF)
cout << D[i][j] << ' ';
else
cout << -1 << ' ';
}
cout << '\n';
}
}
样例测试:
6 8
0 2 10
0 4 30
0 5 100
1 2 5
2 3 50
3 5 10
4 3 20
4 5 60
样例输出:(注意:-1为无法通行)
内容总结
以上是互联网集市为您收集整理的弗洛伊德算法(Floyd)求最短路径全部内容,希望文章能够帮你解决弗洛伊德算法(Floyd)求最短路径所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。