基于Dijkstra算法的网络最短路径分析(2004 李元臣 刘维群 微计算机应用 洛阳师范学院).pdf

第25卷第 3 期 微 计 算 机 应 用 Vol. 25 ,No. 3 2004 年5月 MICROCOMPU TER APPL ICA TIONS Mar. ,2004 基于 Dijkstra 算法的网络最短路径分析 李元臣 　　刘维群 (洛阳师范学院计算机科学系 　洛阳 　471022) 摘要 : 最短路径分析是网络分析最基本的功能之一。Dijkstra 算法是目前公认的较好的最短 路径算法。文章通过对 Dijkstra 算法运行速度分析 , 在该算法的基础上采用二叉树结构来改进 Dijkstra 算法 , 在一定程度上优化了最短路径的计算过程 , 并提高了算法的分析效率 , 实际数据 测试也表明了该算法的可行性。 关键词 : 网络分析　最短路径 　Dijkstra 算法 Analysis of the Shortest Route in Net work on Dijkstra Al gorithm L I Yuanchen , L IU Weiqun (Department of computer science , Luoyang teachers college , Luoyang , 471022 , China) Abstract : The shortest route analysis is one of the fundamental functions in network analysis. Dijk stra Algorithm is an acknowledged better algorithm of shortest route. In this paper , Dijkstra al gorithm is modified by using binary tree structure through analyzing Dijkstra Al gorithms executing speed , which has optimized the calculation process in some degree and improved the efficiency of analysis. This algorithm is feasible by testing some data. Key words : network analysis , shortest route , Dijkstra Al gorithm 最短路径不仅仅指一般意义上的距离最短 , 诸如时间、费用都可被引申为最短路径。相 应地 , 最短路径问题就成为最快路径问题、最低费用问题等。网络分析包括最短路径分析、 资源配置、等时性问题等等 , 但在进行网络分析时 , 还要根据不同的网络 , 建立起相应的网 络分析模型。这里 , 所谓网络模型 , 是指将现实中的地理网络实体 , 抽象化为图论理论中的 网络图 , 并通过图论中的网络分析来实现地理网络的最优化问题[1 ] 。在网络分析中 , 最短 路径问题的分析是最基本的 , 也是最关键的。如今 , 解决最短路径分析问题的方法虽然已经 很成熟 , 例如以 Dijkstra 算法为代表的宽度优先有哪些信誉好的足球投注网站方法 , 许多文献还讨论了 Dijkstra 算法 的实现方法[2 ,3 ] 。但作为网络分析的关键环节 , 由于网络分析的存储量和计算量过于庞大, 最短路径分析算法的效率将直接影响到整个系统的性能。因此对该算法效率的改进历来是人 们研究的