文档介绍：dijkstra最短路径算法
数据通信与计算机网络大作业
Dijkstra
最
短
路
径
算
法
【摘要】
摘要:最短路径分析在地理信息系统、计算机网络路由等方面发挥了重要的作用, 对其进行优化很有必要。本文分析了传统
的最短路径算法(即 Dijkstra 算法)的优化途径及现有的优化算法, 然后在 Dijkstra 算法的基础上, 采用配对堆结构来实现路
径计算过程中优先级队列的一系列操作, 经理论分析与实验测试结果对比, 可以大大提高该算法的效率和性能。
【关键词】
最短路径; Dijkstra 算法;
【正文】
随着计算机网络技术和地理信息科学的发展, 最短路径问题无论是在交通运输, 还是在城市规划、物流管理、网络通讯等方面, 它都发挥了重
要的作用。因此, 对它的研究不但具有重要的理论价值, 而且具有重要的应用价值。研究最短路径问题通常将它们抽象为图论意义下的网络问题, 问题的核心就变成了网络图中的最短路径问题。此时的最短路径不单指“纯距离”意义上的最短路径, 它可以是“经济距离”意义上的最短路径, “时间”意义上的最短路径, “网络”意义上的最短路径。关于最短路径问题, 目前所公认的最好的求解方法, 是由 提出的标号法, 即 Dijkstra 算法。
1 Dijkstra 算法
Dijkstra 算法是求最短路径的最基本和使用最广泛的算法。在求从网络中的某一节点(源点)到其余各节点的最短路径时, 经典 Dijkstra 算法将网络中的节点分成三部分: 未标记节点、临时标记节点和最短路径节点(永久标记节点)。算法开始时源点初始化为最短路径节点, 其余为未标记节点, 算法执行过程中, 每次从最短路径节点往相邻节点扩展, 非最短路径节点的相邻节点修改为临时标记节点, 判断权值是否更新后, 在所有临时标记节点中提取权值最小的节点, 修改为最短路径节点后作为下一次的扩展源, 再重复前面的步骤, 当所有节点都做过扩展源后算法结束。具体算法描述如下:
设在一非负权简单连通无向图 G=<V,E,W>(V:顶点集, E:边集, W:边权值)中, d 为图 G 的邻接矩阵, 求源点 P
0到其余所有节点 Pi的最短路径长度。
⑴将 V 分为未标记节点子集 N、临时最短路径节点子集 T和最短路径节点子集 S, 每个节点上的路径权值为 D(i)。初始化:S={P0}, T=￠, N=V- S,
D(0)=0, D(i)=∞;
⑵更新:将新加入 S 集合的节点 Ps 作为扩展源, 计算从扩展源到相邻节点的路径值。若该值比节点上的原值小, 则用该值替换原值, 否则保持原值不变, 即 D(i)=min{D(s)+d[s][i],D(i)},并将这些相邻节点之中的未标记节点归为临时标记节点, 即T= T∪Pi, N=N- Pi;
⑶选择:在 T 中选择具有最小路径值 D(s)的节点 Ps, 归入集合 S 中, 即 S=S∪Ps, T=T- Ps;
⑷迭代判断:若 T=￠算法结束, 否则转⑵。
该算法总共需要迭代 n- 1 次, 每次迭代都新加一个节点到临时节点集合中, 由于第 i 次迭代时不在临时节点集合中的节点数为 n- i,