正文
路径规划算法之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 = ; //最大边数
const double m_Maxdouble = ; //源点和某点不可达时的距离
int m_Nodenum; //节点的数目
int m_Edgenum; //边的数目
int m_Source; //起始点
int m_DestPoint; //目的地
int m_RecvNum = ; 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:
NULL
Notes:
从“/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 = ;
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 = ;i<=m_Edgenum-;i++)
{
m_Dist[m_Segment[i].m_StartPoint]=m_Maxdouble;
}
m_Dist[m_Source]=;
}
Bellman_Ford();
} /***********************************************************************
Description:
贝尔曼福特函数
Arguments:
NULL
Returns:
NULL
Notes:
松弛路径，记录松弛的路径编号，松弛后标记的路径数量
************************************************************************/
void RoutePlan::Bellman_Ford()
{
for(int i=;i<=m_Nodenum-;i++)
{
for(int j=;j<=m_Edgenum-;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:
NULL
Returns:
return lst 返回路径编号
Notes:
松弛路径，记录松弛的路径编号，松弛后标记的路径数量
************************************************************************/
QList<int> RoutePlan::ReturnPath()
{
QList<int> lst;
for(int k = ; k<m_RecvNum;k++)
{
for(int i = ;i<m_RecvNum;i++)
{
for(int j=;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
