Dijkstra算法的优化.pdf
《Dijkstra算法的优化.pdf》由会员分享,可在线阅读,更多相关《Dijkstra算法的优化.pdf(3页珍藏版)》请在三一文库上搜索。
1、第 13 卷? 第 2 期 2011 年 2 月 天津职业院校联合学报 Journal of Tianjin Vocational Institutes NO. 2 Vol. 13 Feb. 2011 Dijkstra 算法的优化 遇? 娜1, 简广宁2 (1. 天津市红桥区职工大学, 天津市? 300131; 2. 天津城市建设学院, 天津市? 300384) 摘? 要: ? Dijkstra 算法是许多工程解决最短路径问题的理论基础,可用来找出图中指定节点到其他节点的最短 距离,有着广泛的应用。文章通过分析传统 Dijkstra 算法的设计思想, 提出该算法在实现方法上存在的一些不足之 处
2、,并从节约存储空间和提高运算效率方面对其进行了改进, 并通过复杂性分析比较, 得出这种改进算法的效率优于 传统的 Dijkstra 算法。 关键词: ? 最短路径 ;Dijkstra 算法;邻接表; 堆排序 中图分类号: TP312? ? 文献标识码: A? ? 文章编号:1673- 582X(2011)02- 0089- 03 收稿日期: 2010- 11- 10 作者简介: 遇娜(1977- ), 女,天津市人,天津市红桥区职工大学讲师, 从事计算机方面的教学与研究。 最短路径问题是图论研究中一个重要课题。传统公认的求最短路径最好的算法是 Dijkstra 算 法, 它是由荷兰著名的计算机
3、科学家艾兹格 ?迪科斯彻提出来的, 可用来找出图中指定节点到其他节 点的最短距离。其主要思想是从源点求出长度最短的一条路径, 然后通过对路径长度迭代得到从源 点到其他目标节点的最短路径。但随着所解决问题规模的增大, 应用传统的 Dijkstra 算法会使时间 和空间复杂度不断加大。因此, 需对传统的 Dijkstra算法进行了改进, 提出采用邻接表和堆排序的一 种新的优化方法。 一、 传统的 Dijkstra 算法 1. 算法的基本思想 Dijkstra 算法用于计算一个源节点到所有其他节点的最短代价路径, 它是按路径长度递增的次 序来产生最短路径的算法。下面以邻接矩阵描述 Dijkstra
4、算法的实现过程。假设用带权的邻接矩阵 Cost 来表示具有 N 个结点的带权有向图 G3 , Cost i, j 表示弧 的权值, 如果从 Vi 到 Vj 不通, 则 Costi, j= 。引进一个辅助向量 Dist 并设 VS 为起始点, 每个分量 Dist i表示已找到的 从起始点VS 到每个终点 Vi 的最小权值。则该向量的初始值为: Disti= Cost S, iVi ! V。其中, V 是结点的集合。令 S 为已经找到的从起点出发的最短路径的终点集合, 初始值为 S= VS, 则从 VS 出发到图 G 上其它所有结点 Vi 可能达到的最短路径长度为 Disti= Cost S, i
5、Vi ! V。 (1)选择 Vj, 使得 Dj = minDi |Vi ! V- S。Vj 就是当前求得的一条从 VS 出发的最短路 径的终点, 令 S= S Vj。 (2)修改从 VS 到集合 V - S 中任意一顶点 VK 的最短路径长度。如果 D j + Costj, k D k, 则进行第( 3)步。 (3)修改 Dist k 为 Disk k = Dist j + Costj, k; 重复第 2、 3 步操作共 N- 1 次, 由此求得从 VS 到其他顶点的最优路径, 该路径是各权值递增的序列。 2. 算法分析 通过对该算法的仔细分析与研究可以得出, 上述算法中有几点不足之处: (1
6、)用邻接矩阵 Cost 来存储网络图, 其存储量为 N # N。对于大型稀疏矩阵, 这将耗费大量资源 ?89? 存储那些无意义的矩阵元素。 (2) 当从未标记节点集合(V- S)选定下一个节点 Vj 作中间节点后, 在更新操作过程中, 需要扫 描所有的未标记节点并进行比较更新。而未标记节点集合(V- S) 中往往包含大量与中间节点 Vj 不 直接相连的节点。 (3)在选择下一个最短路径节点作为中间节点时, 需要比较所有的未标记节点, 而这个中间节点 往往包含在与已标记节点 S 集合的所有节点邻接的节点中。 (4)在算法的每次迭代中, 由于未标记节点以无序的形式存放在一个链表中或一个数组中, 每
7、次 选择最短路径节点都必须将所有未标记节点扫描一遍, 当节点数目很大时, 这无疑将成为制约计算速 度的关键因素。 二、 Dijkstra算法的优化 针对 Dijkstra算法存在的问题, 我们在数据的组织和存储以及最短路径节点的选取上, 进行了改 进。 1. 优化思路分析 (1)数据组织和数据存储 用邻接矩阵存储图需要开辟 N # N(N 为节点数目) 的存储空间, 对于一个大型稀疏图来说, 计算 效率和存储效率都很低。所以可以采用邻接表来存储网络拓扑结构以节省存储空间。 (2)节点排序和最短路径节点的选取 在改进算法中, 初始时, 待排序的节点以无序形式连续序存放在一个一维数组中, 对其进行
8、堆排 序, 调整成小顶堆后, 各节点即是以完全二叉树的顺序存储结构形式存储, 0 号单元存放的即是调整 后的堆顶元素, 后面依次以左子树、 右子树。在调整堆的过程中时间复杂度为 O( logN) , ( N 为待排 序节点个数) 。与从无序结构下的数组或链表中选择下一个最短路径节点相比较, 明显地节约了时 间, 提高算法执行效率。 2. 改进的 Dijkstra算法基本思想 设置两个集合 S 和 adj 及一个数组 T, S 是已标记集合, adj 是邻接点集, T 存储待排序节点。 初始状态时, S= V0, T= adjV0, 首先, 将数组 T 通过堆排序调整为小顶堆, 取数组首元即堆
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Dijkstra 算法 优化
链接地址:https://www.31doc.com/p-5116550.html