最短路径 bellman-ford
2024-10-19 12:43:57
- 初始化:将除源点外的所有顶点的最短距离估计值 d[v] ←+∞, d[s] ←0
- 迭代求解:反复对边集E中的每条边进行松弛操作,使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离;(运行|v|-1次,看下面的描述性证明(当做树))
- 检验负权回路:判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点,则算法返回false,表明问题无解;否则算法返回true,并且从源点可达的顶点v的最短距离保存在d[v]中
#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 0x3f3f3f3f
#define N 1010
int nodenum, edgenum, original; //点,边,起点
typedef struct Edge //边
{
int u, v;
int cost;
}Edge;
Edge edge[N];
int dis[N], pre[N];
bool Bellman_Ford()
{
for(int i = 1; i <= nodenum; ++i) //初始化
dis[i] = (i == original ? 0 : MAX);
for(int i = 1; i <= nodenum - 1; ++i)
for(int j = 1; j <= edgenum; ++j)
if(dis[edge[j].v] > dis[edge[j].u] + edge[j].cost) //松弛(顺序一定不能反~)
{
dis[edge[j].v] = dis[edge[j].u] + edge[j].cost;
pre[edge[j].v] = edge[j].u;
}
bool flag = 1; //判断是否含有负权回路
for(int i = 1; i <= edgenum; ++i)
if(dis[edge[i].v] > dis[edge[i].u] + edge[i].cost)
{
flag = 0;
break;
}
return flag;
}
void print_path(int root) //打印最短路的路径(反向)
{
while(root != pre[root]) //前驱
{
printf("%d-->", root);
root = pre[root];
}
if(root == pre[root])
printf("%d\n", root);
}
int main()
{
scanf("%d%d%d", &nodenum, &edgenum, &original);
pre[original] = original;
for(int i = 1; i <= edgenum; ++i)
{
scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].cost);
}
if(Bellman_Ford())
for(int i = 1; i <= nodenum; ++i) //每个点最短路
{
printf("%d\n", dis[i]);
printf("Path:");
print_path(i);
}
else
printf("have negative circle\n");
return 0;
}
最新文章
- java中内存分配策略及堆和栈的比较
- Android 手机卫士--九宫格使用
- Java 代码性能优化总结
- Sliverlight中PagedCollectionView的使用
- [转]webrtc学习: 部署stun和turn服务器
- Android apk程序调用其它的APK程序
- flume-agent实例
- DevExpress之列表控件
- CSS 盒子模型(转)
- CodeForces 567B Berland National Library hdu-5477 A Sweet Journey
- mysql 安装错误 解决方法
- studio中碰到的jni问题:java.lang.UnsatisfiedLinkError
- 学习前端笔记1(HTML)
- 自定义扩展实现相对于addRoutes的removeRoutes方法——vue-router
- spring cloud config配置记录
- Requests爬虫
- maven的使用记录
- 维护贴--验证可用--mysql给root开启远程访问权限,修改root密码(转)
- elk6快速安装
- iptables相关操作以及简单理解端口和服务之间关系
热门文章
- cross-compler toolchains--clfs
- linux文件与目录管理命令(ubuntu)
- 重装系统后Myeclipse遇到的项目配置问题--一个菜鸟的经历!
- 3.2 - FTP文件上传下载
- Python 之 UUID
- Python并行编程(一):基本概念
- 一种SPA(单页面应用)架构
- 【HTML5 localStorage本地储存】简介&;基本语法
- java 并发——理解 wait / notify / notifyAll
- XVII Open Cup named after E.V. Pankratiev Stage 14, Grand Prix of Tatarstan, Sunday, April 2, 2017 Problem F. Matrix Game