路径规划算法之Bellman-Ford算法

最近由于工作需要一直在研究Bellman-Ford算法，这也是我第一次用C++编写代码。

1、Bellman-Ford算法总结

（1）Bellman-Ford算法计算从源点（起始点）到任意一点的最短路径的长度，初始化数组m_Dist[m_Segment[i].m_StartPoint] = m_Maxdouble , m_Dist[m_Source]=0。

（2）对每一个路径进行松弛运算

　　如果m_Dist[m_Segment[j].m_EndPoint]>m_Dist[m_Segment[j].m_StartPoint]+m_Segment[j].m_Weight，那么m_Dist[m_Segment[j].m_EndPoint]=m_Dist[m_Segment[j].m_StartPoint]+m_Segment[j].m_Weight进行松弛计算。若上述操作没有对m_Dist进行更新，说明最短路径已经查找完毕，或者部分点不可达，跳出循环。否则执行下次循环；

　　由于规定路径不存在负权重的情况，所以对有负权重的情况这里不进行说明。

注释：m_Source是一条有向边的起点，m_DestPoint是一条有向边的终点；m_Dist(m_StartPoint,m_EndPoint)为节点m_StartPoint和节点m_EndPoint之间边；m_Weight(m_StartPoint, m_EndPoint)为节点m_StartPoint和节点m_EndPoint之间的边的权值；                                                                  m_Dist[m_Segment[i].m_StartPoint] 是指源节点到m_Segment[i].m_StartPoint节点的距离；

下面为本功能模块的代码，由于这只是车载系统中的一部分代码，与其他功能模块存在互相调用的情况，路径信息存在于SQLite数据库找中，读取数据库是一个完整的功能模块，我这里是直接调用就好了。由于这是本人第一次编写C++程序，哪位大神觉得代码有很可以优化的部分，欢迎提出，进行优化！！！

#ifndef ROUTEPLAN_H #define ROUTEPLAN_H#include <qmap.h> #include <QVector> #include <QList> #include <iostream> using namespace std;typedef struct {int m_StartPoint; //线的起始点int m_EndPoint; //线的终点double m_Weight; //线的权重int m_SegmentNum; //有向边编号 }PathPlaning_Segment;class RoutePlan:public QObject {Q_OBJECT public:const static int m_Maxnum = 10000; //最大边数const double m_Maxdouble = 99999999; //源点和某点不可达时的距离int m_Nodenum; //节点的数目int m_Edgenum; //边的数目int m_Source; //起始点int m_DestPoint; //目的地int m_RecvNum = 0;PathPlaning_Segment m_Segment[m_Maxnum]; //路径数组int m_RelaxNum[m_Maxnum]; //松弛的路径编号int m_Dist[m_Maxnum]; //距离数组 RoutePlan();//初始化函数void Init(int srcPoint, int destPoint );//贝尔曼福特函数void Bellman_Ford();//返回路径函数QList<int> ReturnPath(); }; #endif // ROUTEPLAN_H#include "routeplan.h"RoutePlan::RoutePlan() { } /***********************************************************************Description:初始化函数Arguments:int srcPoint 起始点int destPoint 目标点Returns:NULLNotes:从“/home/map.zar”地图文件中读取地图信息，赋值到本地 ************************************************************************/ void RoutePlan::Init(int srcPoint,int destPoint) {m_RouteManager = new RouteManager();if(m_RouteManager->ReadRouteApplicationFile("/home/map.zar")){m_Nodenum = m_RouteManager->ReturnSizeofPoint();m_Edgenum = m_RouteManager->ReturnSizeofSegment();m_Source = srcPoint;m_DestPoint = destPoint;int num = 0;QMap<int,PathApplication_Segments>:: const_iterator iter;QMap<int,PathApplication_Segments> seg = m_RouteManager->ReturnSegment();for( iter=seg.constBegin(); iter!=seg.constEnd(); iter++){m_Segment[num].m_StartPoint = iter.value().StartPointKey;m_Segment[num].m_EndPoint = iter.value().EndPointKey;m_Segment[num].m_Weight = iter.value().Length;m_Segment[num].m_SegmentNum = iter.key();num++;}for(int i = 0;i<=m_Edgenum-1;i++){m_Dist[m_Segment[i].m_StartPoint]=m_Maxdouble;}m_Dist[m_Source]=0;}Bellman_Ford(); }/***********************************************************************Description:贝尔曼福特函数Arguments:NULLReturns:NULLNotes:松弛路径，记录松弛的路径编号，松弛后标记的路径数量 ************************************************************************/ void RoutePlan::Bellman_Ford() {for(int i=0;i<=m_Nodenum-2;i++){for(int j=0;j<=m_Edgenum-1;j++){//松弛路径if(m_Dist[m_Segment[j].m_EndPoint]>m_Dist[m_Segment[j].m_StartPoint]+m_Segment[j].m_Weight){m_Dist[m_Segment[j].m_EndPoint]=m_Dist[m_Segment[j].m_StartPoint]+m_Segment[j].m_Weight;m_RelaxNum[m_RecvNum] = m_Segment[j].m_SegmentNum;m_RecvNum++;}}} } /***********************************************************************Description:返回路径函数Arguments:NULLReturns:return lst 返回路径编号Notes:松弛路径，记录松弛的路径编号，松弛后标记的路径数量 ************************************************************************/ QList<int> RoutePlan::ReturnPath() {QList<int> lst;for(int k = 0; k<m_RecvNum;k++){for(int i = 0;i<m_RecvNum;i++){for(int j=0;j<=m_Edgenum;j++){if(m_RelaxNum[i] == m_Segment[j].m_SegmentNum){if(m_DestPoint == m_Segment[j].m_EndPoint){lst.push_front(m_Segment[j].m_SegmentNum);cout<<"m_SegmentNum = "<<m_Segment[j].m_SegmentNum<<endl;m_DestPoint = m_Segment[j].m_StartPoint;if(m_Segment[j].m_StartPoint == m_Source){return lst;}}}}}}cout<<"there is not path form "<<m_Source<<" to "<<m_DestP

 

转载于:https://www.cnblogs.com/studysoftware/p/10216162.html

总结

以上是生活随笔为你收集整理的路径规划算法之Bellman-Ford算法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。