路径规划算法之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

巴特西

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

最新文章

热门文章