基于Dijkstra的最短路径改进算法(2007 罗理,王锋 湖北汽车工业学院学报 昆明理工).pdf

第 卷第 期 21 2 湖北汽车工业学院学报 Vol.21 No.2 年 月 20076 Jun.2007 基于Dijkstra的最短路径改进算法 罗 理 王 锋 , 昆明理工大学信息工程与自动化学院 云南昆明 ( , ) 650051 摘 要 针对如何利用 算法来高效地查找图中任意两结点之间的最短路径这一问题 提出了 种优化方 : Dijkstra , 2 法 其一是应用图中各结点的出入度来简化查找任意两结点之间的最短路径 其二是利用已求出的两点之间的最 : ; 短路径来快速获得其他结点之间的最短路径。 关键词 最短路径 最短路径算法 算法 出入度 : ; ; ; Dijkstra 中图分类号: 文献标识码: 文章编号: ( ) TP301.6 A 1008-5483200702-0022-04 , LuoLiWangFeng ( , , CollegeofInformationEngineeringandAutomation , ) Kunming65005China : Abstract , , nodesingraphbythealgorithm ofDijkstra which rapidlytheshortestpathamongtheothernodes. : ; ; ; Keywordsshortestpathalgorithm oftheshortestpathalgorithm ofDijkstraout-indegree 随着社会的不断进步 最短路径算法在人们的 是从固定的一个点到其他各点的最短路径问题 但 , 。 日常生活显得越来越重要 比如 每天开车去上班 是在实际生活中往往要求解决的不只是固定一点 。 : , 应该选择哪条公路才能使自己到公司的费用最低 到其他点的最短路径 而是要求计算出任意两点之 、 , 时间最少 这是最短路径的问题 在网络路由中 怎 间的最短距离 针对这个问题 本文主要讨论了怎 , ; ,