DAG中最短路径简单算法

• 作者: 周玉涛
• 来源期刊: 潍坊学院学报
• 学科: 工学
• 关键词: 加权DAG 拓扑排序 边松弛 路径松弛
• 年，卷（期）: 2006,（6）
• 页码范围: 19-21
• 页数: 3页
• 分类号: TP301
• 字数: 1780字
• 语种: 中文
• DOI: 10.3969/j.issn.1671-4288.2006.06.006

摘要

针对DAG的特点,以拓扑排序为基础,提出了解决DAG的最短路径问题的简单算法.通过理论分析,表明该算法具有理想的运算效率,其中,解决单源点问题的运算时间与E成正比,解决所有点对问题的运算时间与VE成正比.拓扑排序策略对于此类最短路径问题的研究,较传统的方法运算简单、求解直观.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	周玉涛		4	2	1.0	1.0