迪杰斯特拉算法数据通信(非正规论文).doc

简单非正规论文 数据通信与计算机网络 网 络 融 合 报 告 通信学院 电子信息工程1303班 1307050330 任前  Dijkstra(迪杰斯特拉)算法 摘要： Dijkstra算法是很有 HYPERLINK /doc/6670661.html \t /doc/_blank 代表性的算法。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法 HYPERLINK /doc/6776575.html \t /doc/_blank 要求图中不 HYPERLINK /doc/5148956.html \t /doc/_blank 存在负权边。Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。 关键词： Dijkstra算法 迪杰斯特拉 单源最短路径算法 引言： 短路径分析在事故抢修、交通指挥、GPS导航等行业应用中使用的非常广泛， 以至于大多数GIS平台都会把这个分析功能作为一个最基础的功能集成进去，如ARCGIS，SuperMap等。个人感觉想要了解这个算法的来龙去脉，一方面是参与相关书籍仔细理解，另外一个最重要的是要去调试代码。由于历史原因，对于书上的伪C代码，我是完全不感兴趣的，而且由于有严格的数学证明，所以看起来相对较难，而对于面向对象实现的算法，我很感兴趣，也感觉很容易理解，所以一边针对C#实现的面向对象代码再一边对照书籍，感觉理解的层次就加深了。 Dijkstra(迪杰斯特拉)的出现 迪杰斯特拉算法是由荷兰计算机科学家 HYPERLINK /view/156673.htm \t /_blank 狄克斯特拉于1959 年提出的，因此又叫 HYPERLINK /view/2541415.htm \t /_blank 狄克斯特拉算法。是从一个顶点到其余各顶点的 HYPERLINK /view/349189.htm \t /_blank 最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。[1]? 中文名 迪克斯特拉算法 外文名 Dijkstras Algorithm 分????类 计算机算法 用????途 单源最短路径问题 定义 Dijkstra算法是典型的 HYPERLINK /view/7420.htm \t /_blank 算法。 HYPERLINK /view/7839.htm \t /_blank Dijkstra算法是很有代表性的 HYPERLINK /view/7420.htm \t /_blank 算法。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用 HYPERLINK /subview/26337htm \t /_blank OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。 相关原理 首先，引进一个辅助向量D，它的每个分量D表示当前所找到的从始点v到每个终点vi的最短路径的长度。如D[3]=2表示从始点v到终点3的路径相对最小长度为2。这里强调相对就是说在算法过程中D的值是在不断逼近最终结果但在过程中不一定就等于最短路径长度。它的初始状态为：若从v到vi有弧，则D为弧上的权值；否则置D为∞。显然，长度为 D[j]=Min{D | vi∈V} 的路径就是从v出发的长度最短的一条最短路径。此路径为(v,vj)。 那么，下一条长度次短的最短路径是哪一条呢？假设该次短路径的终点是vk，则可想而知，这条路径或者是(v,vk)，或者是(v,vj,vk)。它的长度或者是从v到vk的弧上的权值，或者是D[j]和从vj到vk的弧上的权值之和。 一般情况下，假设S为已求得最短路径的终点的集合，则可证明：下一条最短路径（设其终点为X）或者是弧(v,x)，或者是中间只经过S中的顶点而最后到达顶点X的路