Dijkstra算法

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为终点，边上的数字为权值)

　　   

 

 

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