Floyd算法 解决多元汇最短路问题
接下来是图论问题求解最短路问题的最后一个,求解多元汇最短路问题
我们之前一般都是问1-n的最短路径,这里我们要能随便去问i到j的最短路径:
这里介绍一下Floyd算法:我们只有一个d[maxn][maxn]数组直接存储从i到j的最短路径,我们先看代码:
#include<bits/stdc++.h>
#define maxn 210
#define INF 1000000000
using namespace std;
int d[maxn][maxn],n,m,q;
void floyd()
{
for(int k = 1;k<=n;k++)
for(int i = 1;i<=n;i++)
for(int j = 1;j<=n;j++)
d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
}
int main()
{
cin >> n >> m >> q;
for(int i = 1;i<=n;i++)
for(int j = 1;j<=n;j++)
if(i==j) d[i][j] = 0;
else d[i][j] = INF;
while(m--){
int x,y,z;
cin >> x >> y >> z;
d[x][y] = min(d[x][y],z);
}
floyd();
while(q--){
int x,y;
cin >> x >> y;
if(d[x][y] > INF/2) cout << "impossible" << '\n';
else cout << d[x][y] << '\n';
}
return 0;
}
分析:·首先,我们可以看到我们先对d数组进行初始化,使自环为0,其他取INF;
·然后我们读入每条边的数值,我们就要取最小值。是两条直接相连边的边权值最小;
·最后我们直接套三重循环,如下理解:
f[i, j, k]表示从i走到j的路径上除i和j点外只经过1到k的点的所有路径的最短距离。那么f[i, j, k] = min(f[i, j, k - 1), f[i, k, k - 1] + f[k, j, k - 1]。
因此在计算第k层的f[i, j]的时候必须先将第k - 1层的所有状态计算出来,所以需要把k放在最外层
最新文章
- 香蕉云APP,2016下半年开发日记
- 我的MYSQL学习心得(十一) 视图
- python学习笔记(基础四:模块初识、pyc和PyCodeObject是什么)
- SQL Server快速查询某张表的当前行数
- xml 中转意字符&;\/使用方法
- ERP权限系统(七)
- 【KPC】关于为什么不用Zepto而用JQuery
- HeadFirst设计模式之策略模式
- Linux上安装JDK环境变量配置
- SharedPreferences的工具类
- canvas实现视频截图
- Openwrt自定义CGI实现
- java BIO/NIO/AIO 学习
- Squid实现正向代理及访问控制--技术流ken
- 什么是 Native、Web App、Hybrid、React Native 和 Weex?(转载)
- xargs实例
- TF-IDF基本原理
- bit byte哪些事
- asymmetric cryptographic algorithm
- HTTP请求头和响应头总结
热门文章
- 让我一时不知所措 Linux 常用命令 爱情三部曲 下部
- .NET 6全文检索引擎Lucene.NET 4.8简单封装
- php base64格式的图片字符串和图片文件相互转换的代码
- ServiceStack.Redis的源码分析(连接与连接池)
- MySQL常见的函数
- linux系统开机流程
- Visual Studio 2017-2019版本创建C#项目时没有创建网站这一选项?
- 【第一期百题计划进行中,快来打卡学习】吃透java、细化到知识点的练习题及笔试题,助你轻松搞定java
- RFC2889——拥塞控制测试
- 常用windows快捷键及cmd、dos命令