DAG中最短路径简单算法

摘要

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