最近由于工作需要一直在研究Bellman-Ford算法，這也是我第一次用C++編寫(xiě)代碼。

1、Bellman-Ford算法總結(jié)

（1）Bellman-Ford算法計(jì)算從源點(diǎn)（起始點(diǎn)）到任意一點(diǎn)的最短路徑的長(zhǎng)度，初始化數(shù)組m_Dist[m_Segment[i].m_StartPoint] = m_Maxdouble , m_Dist[m_Source]=0。

（2）對(duì)每一個(gè)路徑進(jìn)行松弛運(yùn)算

　　如果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進(jìn)行松弛計(jì)算。若上述操作沒(méi)有對(duì)m_Dist進(jìn)行更新，說(shuō)明最短路徑已經(jīng)查找完畢，或者部分點(diǎn)不可達(dá)，跳出循環(huán)。否則執(zhí)行下次循環(huán)；

　　由于規(guī)定路徑不存在負(fù)權(quán)重的情況，所以對(duì)有負(fù)權(quán)重的情況這里不進(jìn)行說(shuō)明。

注釋：m_Source是一條有向邊的起點(diǎn)，m_DestPoint是一條有向邊的終點(diǎn)；m_Dist(m_StartPoint,m_EndPoint)為節(jié)點(diǎn)m_StartPoint和節(jié)點(diǎn)m_EndPoint之間邊；m_Weight(m_StartPoint, m_EndPoint)為節(jié)點(diǎn)m_StartPoint和節(jié)點(diǎn)m_EndPoint之間的邊的權(quán)值；? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? m_Dist[m_Segment[i].m_StartPoint]?是指源節(jié)點(diǎn)到m_Segment[i].m_StartPoint節(jié)點(diǎn)的距離；

下面為本功能模塊的代碼，由于這只是車(chē)載系統(tǒng)中的一部分代碼，與其他功能模塊存在互相調(diào)用的情況，路徑信息存在于SQLite數(shù)據(jù)庫(kù)找中，讀取數(shù)據(jù)庫(kù)是一個(gè)完整的功能模塊，我這里是直接調(diào)用就好了。由于這是本人第一次編寫(xiě)C++程序，哪位大神覺(jué)得代碼有很可以優(yōu)化的部分，歡迎提出，進(jìn)行優(yōu)化！！！

#ifndef ROUTEPLAN_H #define ROUTEPLAN_H#include <qmap.h> #include <QVector> #include <QList> #include <iostream> using namespace std;typedef struct {int m_StartPoint; //線的起始點(diǎn)int m_EndPoint; //線的終點(diǎn)double m_Weight; //線的權(quán)重int m_SegmentNum; //有向邊編號(hào) }PathPlaning_Segment;class RoutePlan:public QObject {Q_OBJECT public:const static int m_Maxnum = 10000; //最大邊數(shù)const double m_Maxdouble = 99999999; //源點(diǎn)和某點(diǎn)不可達(dá)時(shí)的距離int m_Nodenum; //節(jié)點(diǎn)的數(shù)目int m_Edgenum; //邊的數(shù)目int m_Source; //起始點(diǎn)int m_DestPoint; //目的地int m_RecvNum = 0;PathPlaning_Segment m_Segment[m_Maxnum]; //路徑數(shù)組int m_RelaxNum[m_Maxnum]; //松弛的路徑編號(hào)int m_Dist[m_Maxnum]; //距離數(shù)組 RoutePlan();//初始化函數(shù)void Init(int srcPoint, int destPoint );//貝爾曼福特函數(shù)void Bellman_Ford();//返回路徑函數(shù)QList<int> ReturnPath(); }; #endif // ROUTEPLAN_H#include "routeplan.h"RoutePlan::RoutePlan() { } /***********************************************************************Description:初始化函數(shù)Arguments:int srcPoint 起始點(diǎn)int destPoint 目標(biāo)點(diǎn)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:貝爾曼福特函數(shù)Arguments:NULLReturns:NULLNotes:松弛路徑，記錄松弛的路徑編號(hào)，松弛后標(biāo)記的路徑數(shù)量 ************************************************************************/ 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:返回路徑函數(shù)Arguments:NULLReturns:return lst 返回路徑編號(hào)Notes:松弛路徑，記錄松弛的路徑編號(hào)，松弛后標(biāo)記的路徑數(shù)量 ************************************************************************/ 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

?

轉(zhuǎn)載于:https://www.cnblogs.com/studysoftware/p/10216162.html

總結(jié)

以上是生活随笔為你收集整理的路径规划算法之Bellman-Ford算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。