关键路径与最短路径解析

骑猪看日落 2022-08-20 13:12 574阅读 0赞

1.最短路径：如果从某顶点出发，这个顶点称为源点，经图的边到达另一顶点，这个顶点称为终点，所经过的路径不止一条，找出一条路径使的沿此路径上各边的权值之和为最小。（从源点到终点走得最短的路线权值之和）（默认为1）

2.关键路径：采用边表示活动(Activity On Edge)网络，简称AOE网络。每个顶点代表一个事件，事件说明某些活动或某一项活动的完成，边表示活动，权表示活动持续的时间（关键路径法，也称为统筹方法）。（从源点到汇点完成时间最长路径之和）

发动机实例，影响整个工期或者时间的路径

完成整个计划所需的时间取决于从源点到汇点的最长路径的长度，此长度最大的路径叫做关键路径，也称临界路径。AOE网络只有一个入度为零的点，称为源点；只有一个出度为零的点，称为汇点。

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

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

边的定义如下：

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

节点的定义：

![复制代码][copycode.gif]

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
        }

![复制代码][copycode.gif]

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

![E8_B7_AF_E5_BE_84_E5_88_86_E6_9E_90-_E6_8B_93_E6_89_91_E5_9B_BE.jpg][]

[copycode.gif]: /images/20220731/d3b0e284bb6f4d7593d6e1b5c3987055.png
[E8_B7_AF_E5_BE_84_E5_88_86_E6_9E_90-_E6_8B_93_E6_89_91_E5_9B_BE.jpg]: /images/20220731/042605304d5d495a98dcfbbc831a99a0.png