电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛

标题: 最短路径算法——Dijkstra算法 [打印本页]

作者: yuyang911220 时间: 2016-8-20 19:58 标题: 最短路径算法——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; //权值，代价
}

节点的定义：

[url=]

[/url]
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
}
[url=]

[/url]

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

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

[url=]

[/url]
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; }
      }

作者: yuchengze 时间: 2016-8-21 12:15

很好的代码的分享，感谢分享

欢迎光临电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/)