C++ BellmanFord 最短路径求解算法的两种实现方案

2023-11-01 17:20

本文主要是介绍C++ BellmanFord 最短路径求解算法的两种实现方案,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

概念

贝尔曼-福特算法取自于创始人理查德.贝尔曼和莱斯特.福特,本文简称 BF 算法。BF 算法属于迭代、穷举算法,算法效率较低,如果图结构中顶点数量为 n,边数为 m ,则该算法的时间复杂度为 m*n ,还是挺大的。

核心思想

1、更新顶点的权重: 计算任一条边上一端顶点(始点)到另一个端顶点(终点)的权重。新权重=顶点(始点)权重+边的权重,然后使用新权重值更新终点的原来权重值。

2、更新原则:只有当顶点原来的权重大于新权重时,才更新。

不使用队列

#include <stdio.h>
#include <iostream>
int main()
{int dis[10],bak[10],i,k,n,m,u[10],v[10],w[10],check,flag;int inf=99999;//读入n和m,n表示顶点个数,m表示边的条数scanf("%d %d",&n,&m);//读入边for(i=1; i<=m; i++)scanf("%d %d %d",&u[i],&v[i],&w[i]);//初始化dis数组,这里是1号顶点到其余各个顶点的初始路程for(i=1; i<=n; i++)dis[i]=inf;dis[1]=0;//Bellman-Ford算法核心语句for(k=1; k<=n-1; k++){//将dis数组备份至bak数组中for(i=1; i<=n; i++)bak[i]=dis[i];//进行轮松弛for(i=1; i<=m; i++)if(dis[ v[i] ] > dis[ u[i] ] +w[i]  )dis[ v[i]  ]=dis[ u[i] ]+w[i];check=0;for(i=1; i<=n; i++)if( bak[i]!=dis[i]){check=1;break;}//如果dis数组没有更新,提前退出循环结束算法if(check==0)break;}//检测负权回路flag=0;for(i=1; i<=m; i++)if( dis[v[i]]> dis[u[i]]+w[i]) flag=1;if(flag==1)printf("此图含有负权回路");else{//输出最终的结果for(i=1; i<=n; i++)printf("%d\t",dis[i]);}return 0;
}
//测试用例
5 5
2 3 2
1 2 -3
1 5 5
4 5 2
3 4 3
//输出
0   -3   -1   2    4

Bellman-Ford的队列优化

#include <bits/stdc++.h>using namespace std;
/*
* 顶点类型
*/
struct Ver {//顶点编号int vid=0;//第一个邻接点int head=0;//起点到此顶点的距离(顶点权重),初始为 0 或者无穷大int dis=0;//是否入队bool isVis=false;//重载函数bool operator<( const Ver & ver ) const {return this->dis<ver.dis;}void desc() {cout<<vid<<" "<<dis<<endl;}
};/*
* 边
*/
struct Edge {//邻接点int to;//下一个int next=0;//权重int weight;
};class Graph {private:const int INF=99999;//存储所有顶点Ver vers[100];//存储所有边Edge edges[100];//顶点数,边数int v,e;//起点到其它顶点之间的最短距离int dis[100];//优先队列queue<int> que;public:Graph( int v,int e ) {this->v=v;this->e=e;init();}void init() {for(int i=1; i<=v; i++) {//重置顶点信息vers[i].vid=i;vers[i].dis=INF;vers[i].head=0;vers[i].isVis=false;}int f,t,w;for(int i=1; i<=e; i++) {cin>>f>>t>>w;//设置边的信息edges[i].to=t;edges[i].weight=w;//头部插入edges[i].next=vers[f].head;vers[f].head=i;}for(int i=1; i<=v; i++) {dis[i]=vers[i].dis;}}void spfa(int start) {//初始化队列,起点到起点的距离为 0vers[start].dis=0;dis[start]=0;vers[start].isVis=true;que.push(start);while( !que.empty() ) {//出队列Ver ver=vers[  que.front()  ];ver.desc();que.pop();//找到邻接顶点 i 是边集合索引号for( int i=ver.head; i!=0; i=edges[i].next) {int v=edges[i].to;//更新距离if( vers[ v ].dis > ver.dis + edges[i].weight ) {vers[ v ].dis = ver.dis+edges[i].weight;dis[ v ]= vers[ v ].dis;}//入队列 有可能更新了队列中没有更新if( vers[ v ].isVis==false ) {vers[ v ].isVis=true;que.push( v );}}}}void show() {for(int i=1; i<=v; i++) {cout<<dis[i]<<"\t";}}};int main() {int v,e;cin>>v>>e;Graph graph(v,e);graph.spfa(1);graph.show();return 0;
}
//测试用例
5 7
1 2 2
1 5 10
2 3 3
2 5 7
3 4 4
4 5 5
5 3 6
//输出
0  2 5  9  9

这篇关于C++ BellmanFord 最短路径求解算法的两种实现方案的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/324542

相关文章

分布式锁在Spring Boot应用中的实现过程

《分布式锁在SpringBoot应用中的实现过程》文章介绍在SpringBoot中通过自定义Lock注解、LockAspect切面和RedisLockUtils工具类实现分布式锁,确保多实例并发操作... 目录Lock注解LockASPect切面RedisLockUtils工具类总结在现代微服务架构中,分布

Java使用Thumbnailator库实现图片处理与压缩功能

《Java使用Thumbnailator库实现图片处理与压缩功能》Thumbnailator是高性能Java图像处理库,支持缩放、旋转、水印添加、裁剪及格式转换,提供易用API和性能优化,适合Web应... 目录1. 图片处理库Thumbnailator介绍2. 基本和指定大小图片缩放功能2.1 图片缩放的

Python使用Tenacity一行代码实现自动重试详解

《Python使用Tenacity一行代码实现自动重试详解》tenacity是一个专为Python设计的通用重试库,它的核心理念就是用简单、清晰的方式,为任何可能失败的操作添加重试能力,下面我们就来看... 目录一切始于一个简单的 API 调用Tenacity 入门:一行代码实现优雅重试精细控制:让重试按我

Python安装Pandas库的两种方法

《Python安装Pandas库的两种方法》本文介绍了三种安装PythonPandas库的方法,通过cmd命令行安装并解决版本冲突,手动下载whl文件安装,更换国内镜像源加速下载,最后建议用pipli... 目录方法一:cmd命令行执行pip install pandas方法二:找到pandas下载库,然后

Redis客户端连接机制的实现方案

《Redis客户端连接机制的实现方案》本文主要介绍了Redis客户端连接机制的实现方案,包括事件驱动模型、非阻塞I/O处理、连接池应用及配置优化,具有一定的参考价值,感兴趣的可以了解一下... 目录1. Redis连接模型概述2. 连接建立过程详解2.1 连php接初始化流程2.2 关键配置参数3. 最大连

Python实现网格交易策略的过程

《Python实现网格交易策略的过程》本文讲解Python网格交易策略,利用ccxt获取加密货币数据及backtrader回测,通过设定网格节点,低买高卖获利,适合震荡行情,下面跟我一起看看我们的第一... 网格交易是一种经典的量化交易策略,其核心思想是在价格上下预设多个“网格”,当价格触发特定网格时执行买

python设置环境变量路径实现过程

《python设置环境变量路径实现过程》本文介绍设置Python路径的多种方法:临时设置(Windows用`set`,Linux/macOS用`export`)、永久设置(系统属性或shell配置文件... 目录设置python路径的方法临时设置环境变量(适用于当前会话)永久设置环境变量(Windows系统

C++11范围for初始化列表auto decltype详解

《C++11范围for初始化列表autodecltype详解》C++11引入auto类型推导、decltype类型推断、统一列表初始化、范围for循环及智能指针,提升代码简洁性、类型安全与资源管理效... 目录C++11新特性1. 自动类型推导auto1.1 基本语法2. decltype3. 列表初始化3

C++11右值引用与Lambda表达式的使用

《C++11右值引用与Lambda表达式的使用》C++11引入右值引用,实现移动语义提升性能,支持资源转移与完美转发;同时引入Lambda表达式,简化匿名函数定义,通过捕获列表和参数列表灵活处理变量... 目录C++11新特性右值引用和移动语义左值 / 右值常见的左值和右值移动语义移动构造函数移动复制运算符

Python对接支付宝支付之使用AliPay实现的详细操作指南

《Python对接支付宝支付之使用AliPay实现的详细操作指南》支付宝没有提供PythonSDK,但是强大的github就有提供python-alipay-sdk,封装里很多复杂操作,使用这个我们就... 目录一、引言二、准备工作2.1 支付宝开放平台入驻与应用创建2.2 密钥生成与配置2.3 安装ali