最短路径算法——Dijkstra算法_用dijkstra算法在栅格图中走最短路径-程序员宅基地

最短路径算法——Dijkstra算法    

    Dijkstra 算法在刚开始在学数据结构的时候,完全没弄明白,主要是也不怎么想去弄明白。而从学校出来到现在,最短路径算法都没有实际运用过,最近在一个GIS项目中总算用到了,于是乎把教材重温了下,同时查阅了网上一些资料,借鉴了一些别人的东西,并顺利用写进了项目中,文中的主要代码来自于园子里的一位大哥,这位大哥对通用框架的研究很深入,他的链接为:http://zhuweisky.cnblogs.com/archive/2005/09/29/246677.html(最短路径)。另外,文章的最后面的一些链接是我找资料的时候用到过的,有兴趣

的朋友可以去看看。

最短路径分析在事故抢修、交通指挥、GPS导航等行业应用中使用的非常广泛, 以至于大多数GIS平台都会把这个分析功能作为一个最基础的功能集成进去,如ARCGIS,SuperMap等。个人感觉想要了解这个算法的来龙去脉,一方面是参与相关书籍仔细理解,另外一个最重要的是要去调试代码。由于历史原因,对于书上的伪C代码,我是完全不感兴趣的,而且由于有严格的数学证明,所以看起来相对较难,而对于面向对象实现的算法,我很感兴趣,也感觉很容易理解,所以一边针对C#实现的面向对象代码再一边对照书籍,感觉理解的层次就加深了。

 Dijkstra算法又称为单源最短路径,所谓单源是在一个有向图中,从一个顶点出发,求该顶点至所有可到达顶点的最短路径问题。要顺利实现算法,要求理解Dijstra的算法,同时还要理解图的一些基本概念,图由节点和边构成,将节点和边看成对象,每个对象有自己的特有属性,如在GIS中,一个节点必须都有ID,横坐标,纵坐标等基本属性,边有起点节点,终点节点,长度等属性,而最短路径分析,就是根据边的长度(权值)进行分析的。

边的定义如下:

     

    public   class  Edge
    {
        
public   string  StartNodeID;
        
public   string  EndNodeID;
        
public   double  Weight;  // 权值,代价        
    }

 

      节点的定义:

     

复制代码
    public   class  Node
    {
        
private   string  iD ;
        
private  List < Edge >  edgeList ; // Edge的集合--出边表

        
public  Node( string  id )
        {
            
this .iD  =  id ;
            
this .edgeList  =   new   List < Edge > () ;
        }

       
#region  property
        
        
public   string  ID
        {
            
get
          {
                
return   this .iD ;
            }
        }

        
public  List < Edge >   EdgeList
        {
            
get
            {
                
return   this .edgeList ;
            }
        }
        
#endregion
    }
复制代码

 

      本次用于分析的拓扑图如下:(A为起点,D为终点,边上的数字为权值)

     

 

 

      利用上述的边与节点的定义,可以通过代码简单的构成如下图:

     

复制代码
    public   class  Graph
    {
        
public  List < Node >  m_nodeList  =   null ;
        
public  Graph()
        {
            m_nodeList 
=   new  List < Node > ();
        }

        
///   <summary>
        
///  获取图的节点集合
        
///   </summary>
         public  List < Node >  NodeList
        {
            
get  {  return   this .m_nodeList; }
        }

        
///   <summary>
        
///  初始化拓扑图
        
///   </summary>
         public   void  Init()
        {
            
// ***************** B Node *******************
            Node aNode  =   new  Node( " A " );
            m_nodeList.Add(aNode);
            
// A -> B
            Edge aEdge1  =   new  Edge();
            aEdge1.StartNodeID 
=  aNode.ID;
            aEdge1.EndNodeID 
=   " B " ;
            aEdge1.Weight 
=   10 ;
            aNode.EdgeList.Add(aEdge1);
            
// A -> C
            Edge aEdge2  =   new  Edge();
            aEdge2.StartNodeID 
=  aNode.ID;
            aEdge2.EndNodeID 
=   " C " ;
            aEdge2.Weight 
=   20 ;
            aNode.EdgeList.Add(aEdge2);
            
// A -> E
            Edge aEdge3  =   new  Edge();
            aEdge3.StartNodeID 
=  aNode.ID;
            aEdge3.EndNodeID 
=   " E " ;
            aEdge3.Weight 
=   30 ;
            aNode.EdgeList.Add(aEdge3);

            
// ***************** B Node *******************
            Node bNode  =   new  Node( " B " );
            m_nodeList.Add(bNode);
            
// B -> C
            Edge bEdge1  =   new  Edge();
            bEdge1.StartNodeID 
=  bNode.ID;
            bEdge1.EndNodeID 
=   " C " ;
            bEdge1.Weight 
=   5 ;
            bNode.EdgeList.Add(bEdge1);
            
// B -> E
            Edge bEdge2  =   new  Edge();
            bEdge2.StartNodeID 
=  bNode.ID;
            bEdge2.EndNodeID 
=   " E " ;
            bEdge2.Weight 
=   10 ;
            bNode.EdgeList.Add(bEdge2);

            
// ***************** C Node *******************
            Node cNode  =   new  Node( " C " );
            m_nodeList.Add(cNode);
            
// C -> D
            Edge cEdge1  =   new  Edge();
            cEdge1.StartNodeID 
=  cNode.ID;
            cEdge1.EndNodeID 
=   " D " ;
            cEdge1.Weight 
=   30 ;
            cNode.EdgeList.Add(cEdge1);

            
// ***************** D Node *******************
            Node dNode  =   new  Node( " D " );
            m_nodeList.Add(dNode);

            
// ***************** E Node *******************
            Node eNode  =   new  Node( " E " );
            m_nodeList.Add(eNode);
            
// E -> D
            Edge eEdge1  =   new  Edge();
            eEdge1.StartNodeID 
=  eNode.ID;
            eEdge1.EndNodeID 
=   " D " ;
            eEdge1.Weight 
=   20 ;
            eNode.EdgeList.Add(eEdge1);
        }
    }
复制代码

 

 

    

      有了拓扑节点和边,就可以根据算法构造其他最短路径分析的对象了,主要步骤如下:

Ø  初始化图中的从A出发的路径集合:

  

复制代码
    ///   <summary>
    
///  PlanCourse 缓存从源节点到其它任一节点的最小权值路径(路径表)
    
///   </summary>
     public   class  PlanCourse
    {
        
private  Hashtable htPassedPath;

        
#region  ctor
        
public  PlanCourse(List < Node >  nodeList,  string  originID)
        {
            
this .htPassedPath  =   new  Hashtable();

            Node originNode 
=   null ;
            
foreach  (Node node  in  nodeList)
            {
                
if  (node.ID  ==  originID)
                {
                    originNode 
=  node;
                }
                
else
                {
                    PassedPath pPath 
=   new  PassedPath(node.ID);
                    
this .htPassedPath.Add(node.ID, pPath);
                }
            }

            
if  (originNode  ==   null )
            {
                
throw   new  Exception( " The origin node is not exist ! " );
            }

            
this .InitializeWeight(originNode);
        }

        
///   <summary>
        
///  通过指定节点的边的权值初始化路径表
        
///   </summary>
        
///   <param name="originNode"></param>
         private   void  InitializeWeight(Node originNode)
        {
            
if  ((originNode.EdgeList  ==   null ||  (originNode.EdgeList.Count  ==   0 ))
            {
                
return ;
            }

            
foreach  (Edge edge  in  originNode.EdgeList)
            {
                 PassedPath pPath 
=   this [edge.EndNodeID];
                
if  (pPath  ==   null )
                {
                    
continue ;
                }

                pPath.PassedIDList.Add(originNode.ID);
                pPath.Weight 
=  edge.Weight;
            }
        }
        
#endregion

        
///   <summary>
        
///  获取指定点的路径表
        
///   </summary>
        
///   <param name="nodeID"></param>
        
///   <returns></returns>
         public  PassedPath  this [ string  nodeID]
        {
            
get
            {
                
return  (PassedPath) this .htPassedPath[nodeID];
            }
        }
    }
复制代码

 

 

Ø  从A中最短路径集合中找到一个最短的路径点Vi开始分析

 

复制代码
        ///   <summary>
        
///  从PlanCourse取出一个当前累积权值最小,并且没有被处理过的节点
        
///   </summary>
        
///   <returns></returns>
         private  Node GetMinWeightRudeNode(PlanCourse planCourse, List < Node >  nodeList,  string  originID)
        {
            
double  weight  =   double .MaxValue;
            Node destNode 
=   null ;

            
foreach  (Node node  in  nodeList)
            {
                
if  (node.ID  ==  originID)
                {
                    
continue ;
                }

                PassedPath pPath 
=  planCourse[node.ID];
                
if  (pPath.BeProcessed)
                {
                    
continue ;
                }

                
if  (pPath.Weight  <  weight)
                {
                    weight 
=  pPath.Weight;
                    destNode 
=  node;
                }
            }

            
return  destNode;
        }
复制代码

 

Ø  修正从A出发至Vi最短路径,并重新选择另一个最短路径点Vj点开始分析,重新执行上述步骤的路径分析

   

复制代码
            while  (curNode  !=   null )
            {
                PassedPath curPath 
=  planCourse[curNode.ID];
                
foreach  (Edge edge  in  curNode.EdgeList)
                {
                    PassedPath targetPath 
=  planCourse[edge.EndNodeID];
                    
double  tempWeight  =  curPath.Weight  +  edge.Weight;

                    
if  (tempWeight  <  targetPath.Weight)
                    {
                        targetPath.Weight 
=  tempWeight;
                        targetPath.PassedIDList.Clear();

                        
for  ( int  i  =   0 ; i  <  curPath.PassedIDList.Count; i ++ )
                        {
                            targetPath.PassedIDList.Add(curPath.PassedIDList[i].ToString());
                        }

                        targetPath.PassedIDList.Add(curNode.ID);
                    }
                }

                
// 标志为已处理
                planCourse[curNode.ID].BeProcessed  =   true ;
                
// 获取下一个未处理节点
                 curNode  =   this .GetMinWeightRudeNode(planCourse, nodeList, originID);
            }
复制代码

 

 

Ø  重复上述两个步骤,一直到所有的对象都分析完为止。

Ø  这个时候的路径集合表中已经保存了从A到任意一点的最短路径集合了。

     

复制代码
        ///   <summary>
        
///  从PlanCourse表中取出目标节点的PassedPath,这个PassedPath即是规划结果
        
///   </summary>
        
///   <returns></returns>
         private  RoutePlanResult GetResult(PlanCourse planCourse,  string  destID)
        {
            PassedPath pPath 
=  planCourse[destID];

            
if  (pPath.Weight  ==   int .MaxValue)
            {
                RoutePlanResult result1 
=   new  RoutePlanResult( null int .MaxValue);
                
return  result1;
            }

            
string [] passedNodeIDs  =   new   string [pPath.PassedIDList.Count];
            
for  ( int  i  =   0 ; i  <  passedNodeIDs.Length; i ++ )
            {
                passedNodeIDs[i] 
=  pPath.PassedIDList[i].ToString();
            }

            RoutePlanResult result 
=   new  RoutePlanResult(passedNodeIDs, pPath.Weight);

            
return  result;
        }
复制代码

 

   最短路径的结果类定义如下:

   

复制代码
    public   class  RoutePlanResult
    {
        
public  RoutePlanResult( string [] passedNodes,  double  value)
        {
            m_resultNodes 
=  passedNodes;
            m_value 
=  value;
        }

        
private   string [] m_resultNodes;
        
///   <summary>
        
///  最短路径经过的节点
        
///   </summary>
         public   string [] ResultNodes
        {
            
get  {  return  m_resultNodes; }
        }

        
private   double  m_value;
        
///   <summary>
        
///  最短路径的值
        
///   </summary>
         private   double  Value
        {
            
get  {  return  m_value; }
        }
    }
复制代码

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/lewutian/article/details/8169413

智能推荐

swift 去除tableview 中多余的分割线_swift tableview 去掉分割线-程序员宅基地

文章浏览阅读2.8k次。swift 去除tableview 中多余的分割线// 去除多余的分割线let view = UIView(frame: CGRectZero)self.tableView.tableFooterView = view_swift tableview 去掉分割线

Matlab R2014b 下载与安装-程序员宅基地

文章浏览阅读1.8k次。链接:http://pan.baidu.com/s/1pJA08jh 密码:3hlh内含安装破解步骤 一定注意要拔断网才可以破解

连接sqlserver2005数据库-程序员宅基地

文章浏览阅读177次。import java.sql.*; public class ConnSqlServer2005 { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub try { ConnSqlServer2005 sql = new ConnSq..._sql2005连接数据库

sdl2 for android ubuntu开发环境搭建记录,编译SDL2 on ubuntu 16.04 x64_sdl2库(1)-移植android 端 ubuntu-程序员宅基地

文章浏览阅读1.6k次。SDL2 linux开发环境搭建记录,2016.09.28搭建成功,编译通过,sdl2 ubunt开发环境搭建记录:ubunt编译SDL2.0.4详细教程,ubuntu编译SDL2详细过程:ubuntu 16.04 x64虚拟机安装SDL2.0.4的工作记录,ubuntu搭建SDL2开发环境的过程记录:设置环境变量,开发 android要切换到root用户: 下载目前SDL官网最新的开发包SDL_sdl2库(1)-移植android 端 ubuntu

java8 stream reduce()方法使用_java stream reduce方法-程序员宅基地

文章浏览阅读7k次。java8 stream reduce()方法使用_java stream reduce方法

MAC M1 芯片在 yarn install 时报错:The CPU architecture “arm64“_the cpu architecture "x64" is incompatible with th-程序员宅基地

文章浏览阅读2.6k次。新公司新电脑,最强 M1 芯片 MAC,兴高采烈装环境:nvm、node、yarn…然鹅,yarn install 装包时给了我重头一击…背景首先我用下面命令安装了 nvm:curl -o- https://raw.githubusercontent.com/creationix/nvm/v0.38.0/install.sh | bash然后用 nvm 安装了 node,然后用下面命令安装了 yarncurl -o- -L https://yarnpkg.com/install.sh |._the cpu architecture "x64" is incompatible with this module.

随便推点

QT5的软键盘输入法实现_qt_im_module-程序员宅基地

文章浏览阅读6.4k次,点赞2次,收藏21次。目录(?)[-]一为什么要用输入法的方式实现二QT5输入法插件的结构三具体实现四测试五说明一、为什么要用输入法的方式实现要实现点击一个编辑框就跳出来一个软键盘方法很多,为什么要用输入法的方式呢?输入法的方式可以用在任一个QT程序上,而应用程序本身不需要去关心如何去输入,交给输入法就可以了。输入法与程序是独立的,两个程序通过通信的方式进行对话。就比如我们在手机上写_qt_im_module

[Node.js框架学习笔记]Koa框架初体验_npm install koa-generator -g-程序员宅基地

文章浏览阅读243次,点赞2次,收藏2次。Koa框架Koa框架简介Koa初体验初始化框架1.安装框架生成器`npm install koa-generator -g`2.使用命令创建文件`koa2 koa2_stu`3.cd 到目录下使用`npm install`安装默认的框架依赖4.安装模块引擎和数据库依赖`npm install art-template koa-art-template mysql`5.修改app.js文件6.测试 `npm start`初始化模型1.创建models目录->创建stu.js模型文件2.修改app.js创_npm install koa-generator -g

绩点计算···_1. 绩点计算器 输入:一个成绩单文件 grade.txt每行一个字符串、两个整数,用空格隔-程序员宅基地

文章浏览阅读389次。题目描述【问题描述】学校对本科生的成绩施行绩点制(GPA)。将学生的实际考分根据不同学科的不同学分按一定的公式进行计算。规定如下:实际成绩 绩点90-100 4.085-89 3.782-84 3.378-81 3.075-77 2.772-74 2.368-71 2.064-67 1.560-63 _1. 绩点计算器 输入:一个成绩单文件 grade.txt每行一个字符串、两个整数,用空格隔

C语言中malloc()函数与alloc()函数_alloc 汇编语言中什么意思-程序员宅基地

文章浏览阅读842次。C语言跟内存分配方式  (1) 从静态存储区域分配。内存在程序编译的时候就已经分配好,这块内存在程序的整个运行期间都存在。例如全局变量,static变量。  (2) 在栈上创建。在执行函数时,函数内局部变量的存储单元都可以在栈上创建,函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中,效率很高,但是分配的内存容量有限。  (3)从堆上分配,亦称动态内存分配。程序_alloc 汇编语言中什么意思

VUE 使用echarts线图,常用配置属性介绍_vue的echarts等值线图-程序员宅基地

文章浏览阅读730次。VUE 使用echarts线图,常用属性介绍文章就是介绍应该会用得上的属性设置。这里不是安装教学哈,安装教学出门左转!介绍全在代码的备注中,请慢慢食用!methods: { myEcharts() { var that = this // 基于准备好的dom,初始化echarts实例 var myChart = this.$echarts.init(document.getElementById("main")); // 指定图表的配置项和数据 _vue的echarts等值线图

no xxx in java.library.path问题_no mrapi in java.library.path-程序员宅基地

文章浏览阅读593次。java一般使用两个path:classpath 和 java.library.pathclasspath是指向jar包的位置java.library.path是非java类包的位置如(dll,so)是由于在tomcat的启动文件catalina.sh中JAVA_OPTS中指定了java.library.path..._no mrapi in java.library.path