一种改进的最短路径算法

摘要：

求最短路径，是一个应用很广泛的问题，求最短路径的算法有很多，公认较好的算法是由Dijkstra于195g年提出的标号法。但是算法实验表明，标号法有需要改进的地方：①算法的退出机制对有向图有可能无效，甚至会陷入死循环；②标号法没有涉及最短路径上顶点的邻接点问题；③标号法没有涉及多个顶点同时获得p标号的问题。针对上述问题，本文对标号法进行了改进。算法实验表明，改进的标号法能够有效解决上述问题。

关键词： 最短路径 标号法 算法实验 退出机制

作者: 王树西 夏增艳

作者单位: 对外经济贸易大学信息学院 北京 100029 北京邮电大学民族学院 北京 102209

会议类型: 国内会议

会议名称: 全国第十五届离散数学学术研讨会

会议地点: 南京

会议语种:中文

页码: 12-14,34

在线出版日期: 2010-08-01（万方平台首次上网日期，不代表论文的发表时间）