DAG中最短路径简单算法

摘要：

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

关键词：加权DAG、拓扑排序、边松弛、路径松弛

所属期刊栏目：6

分类号：TP301(计算技术、计算机技术)

在线出版日期：2007-06-04（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：19-21