改进的最短路径矩阵迭代标号法

• 作者: 潘虹 薛瑞 黄式东
• 来源期刊: 现代计算机：中旬刊
• 学科: 数学
• 关键词: DIJKSTRA算法 最短路径 矩阵算法
• 年，卷（期）: 2015,（9）
• 页码范围: 3-6
• 页数: 4页
• 分类号: O157.5

摘要

最短路径模型是图论研究中的经典问题,针对传统的Dijkstra算法的不足,提出改进的矩阵迭代标号法。改进算法不仅可以有效地求解负权值最短路径问题,而且当两点间存在多条最短路径时,改进算法可以同时得到所有的最短路径。实验结果表明,改进算法的时间复杂度低于传统的Dijkstra算法,且算法简单、易于实现。