1 / 15
文档名称:

Dijkstra最短路径算法.docx

格式:docx   大小:198KB   页数:15页
下载后只包含 1 个 DOCX 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

Dijkstra最短路径算法.docx

上传人:beny00011 2022/1/12 文件大小:198 KB

下载得到文件列表

Dijkstra最短路径算法.docx

相关文档

文档介绍

文档介绍:word
word
1 / 15
word
Dijkstra最短路径算法
word
word
2 / 15
word
摘 要
OSPF 是由 IETF 的 IGP 工作组为 IP 网开发的一种能适应大型网络需要的典型的 链路状态路由协议,它可以迅速地检测 AS 内的拓扑变化,经过一个比拟短的收敛期 后,重新计算出无环路由。在 OSPF 中采用的是 Dijkstra 算法来实现最短路径的计算, 做到了选路的高效、可靠。不同的算法在时间上的开销是不一样的,可能会有很大 的差异,而对于一个大型的网络来讲,选路的效率往往就是网络的生命,算法的重 要性不言而喻。
关键词 OSPF 最短路径Dijkstra
word
word
3 / 15
word
第1章 绪论
最短路径算法是计算机科学与地理信息科学等领域研究的热点,其算法有很多种,其中传统的Dijkstra算法一般用于计算一个源节点到所有其他节点的最小代价路径,并且能够适应网络拓扑的变化,性能稳定,因而可以在运输路线规划等领域都应用广泛.
国内外最短路径算法的开展与其概况
最短路径在20世纪初开始受到人们的重视,关于它的求解方法,当时有很多科学家在研究.但给出求解的根本思想的人直到1959年才出现,是一位名叫Edsger Wybe Dijkstra〔迪杰斯特拉〕的荷兰计算机科学家,他不仅给出了求解的根本思想,还给出了算法.他给出的算法主要解决的问题是从某一个固定的点到其他各点的最短路径问题.后来这个算法被誉为一代经典,被称作Dijkstra算法.后来,人们逐渐从两个方面来研究最短路径,分为完全信息情况下和不确定情况下.确定情况下对最短路径的研究的过程中,开展出了很多高效的算法,其中1958年的Bellman算法、1959年的Dijkstra算法、1969年的Dreyfus算法已成为确定情况下的经典算法[1].而不确定情况下对最短问题的研究又分成了四个方面:研究路段长度随机变化的最短路径问题,以Frank和Mirchandani为代表;研究不同费用函数最短路径问题,以Loui、Muethy和Sarkar为代表;研究时间独立情况下的路段长度随机变化的最短路径问题,Hall、LiPing Fu、、Elise和Hani为代表;研究路段长度为区间X围的最短路径问题,以Tomas和Rajeev为代表.其中,第二方面问题的研究得出的结论是“当目标是期望最短路径时问题转化为将边的权重用期望值表示的最短路径问题〞.
word
word
5 / 15
word
传统Dijkstra算法仍然存在的一些问题
原始Dijkstra算法在存储图形数据和运算时,基于网络的权矩阵,需要根据其节点与距离之间的关系,形成关联矩阵、邻接矩阵与距离矩阵,需要定义的数组来存储数据,其中为网络的节点数,当网络的节点数较大时,将占用大量的计算机内存.
原始Dijkstra算法在运行时一般将网络节点分为未标记节点、临时标记节点和永久标记节点3种类型.网络中所有节点首先初始化为未标记节点,在搜索过程中和最短路径节点相连通的节点为临时标记节点,每一次循环都是从临时标记节点中搜索距离原点路径长度最短的节点作为永久标记节点,直至找到目标节点或者所有节点都成为永久标记节点才完毕算法.根据算法的描述可知对临时标记节点的遍历成为Dijkstra算法的瓶颈,影响了算法的执行效率.
第2章 Dijkstra经典算法
引言
Dijkstra算法是典型最短路算法,用于计算一个节点到其他所有节点的最短路径.主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止.Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低.如何改良这一经典算法,成为了实现图论中赋权图中解决实际问题的重要课题.
原理与应用
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径.主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止.Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为根本内容有详细的介绍,如数据结构,图论,运筹学等等.Dijkstra一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN, CLOSE表的方式,这里均采用永久和临时标号的方式.该算法要求图中不存在负权边.
word
word
5 / 15
word
原理
Dijkstra算法是1959年由E.W.Dijkstra

最近更新

针织用纱质量浅析 3页

采用精密距离测量在基坑平面位移中的应用 3页

《山中访友》教学设计 32页

连铸圆坯结晶器锥度优化设计研究 3页

辐照前处理木质纤维素的研究进展 3页

超声波淬火工艺在40Cr阶梯轴淬火中的应用 3页

论XBRL分类标准扩展——以石油天然气行业为例.. 3页

西非地区路网规划特点及公路建设发展研究 3页

行政事业单位内控测试评价、缺陷与优化探析 4页

表演动作猜成语素材 111页

苏54区块盒 8段储层气水分布特征及识别方法研.. 3页

2025年农村住房租赁市场租赁合同租赁权转让合.. 8页

职业企业家行为失范机理分析及其约束机制研究.. 3页

绩效考核在医院人力资源管理中的应用研究 3页

蒸发和降水的观测 57页

第六届粤港澳大湾区“粤菜师傅”技能大赛中式.. 13页

福建省旅游业发展前景SWOT分析 3页

硬质合金自动切菜机刀具设计及工艺优化 4页

石油销售企业竞争力的增强方式分析与研究 3页

苏霍姆林斯基给教师的100条建议之 9页

2025年鼓励孩子多读书的金句 7页

2025年鸡年农历九月宝宝取名技巧 4页

2025年高考选科选物理一定要选化学吗 4页

2025年高考毕业串场词 20页

苏卫单招校测2025试卷 9页

《黄河颂》33694省公开课一等奖全国示范课微课.. 29页

部编版九年级语文上册必背古诗文 8页

消毒小车策划书 4页

3D打印技术与虚拟现实的融合 26页

党建调研提纲 2页