基于不含负长度环有向图的Dijkstra算法

• 作者: 尹方 邓壮
• 来源期刊: 重庆邮电学院学报（自然科学版）
• 学科: 工学
• 关键词: Dijkstra算法 单源点最短路径 正权有向图 负长度环
• 年，卷（期）: 2006,（z1）
• 所属期刊栏目: 计算机与自动化
• 页码范围: 218-220
• 页数: 3页
• 分类号: TP301.6
• 字数: 2349字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-825X.2006.z1.066

摘要

Dijkstra算法是目前公认的较好的最短路径算法,单源点最短路径问题是最短路径问题家族中的核心问题之一.介绍了基于单源点最短路径问题在假定正权有向图上工作的Dijkstra算法以及算法的时间复杂度,同时又介绍了作了功能改进后的Dijkstra算法以及时间复杂度分析,并给出了算法实际工作于不合负长度环有向图的过程和结果.作了功能上的改进后,其算法能正常工作于不含负长度环的带权有向图中.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	尹方	重庆邮电大学应用技术学院	5	17	2.0	4.0
2	邓壮	重庆邮电大学应用技术学院	2	3	1.0	1.0