无回路网络最短路径的一种新算法

• 作者: 蒋腾飞 赵礼峰
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 最短路 无回路网络 有效算法 双向弧
• 年，卷（期）: 2013,（2）
• 页码范围: 105-107
• 分类号: TP311
• 字数: 2151字
• 语种: 中文
• DOI: 10.3969/j.jssn.1673-2013.02.026

摘要

对于求解小规模无回路网络的最短路径这一问题,目前大多数算法都是基于Dijkstra算法或者穷举法的思想,不仅计算量大而且操作复杂.文中在深入分析已有算法的基础上,给出了一种新的简单易行的方法.该算法通过不断消去中间节点和弧以简化图的结构,既能快速地计算出源点到目的节点的最短路径,又能直观地找出最短路.最后算法通过具体实例分析表明,该算法不仅思想简便、易于操作,同时有效地降低了算法复杂度,是计算小规模无回路网络的一种行之有效的算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵礼峰	南京邮电大学理学院	47	251	9.0	12.0
2	蒋腾飞	南京邮电大学理学院	1	7	1.0	1.0