本文主要是介绍算法导论——24.2 DAG最短路径算法java实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
介绍
Bellman-Ford算法能在更普遍的情况下（存在负权边）解决单源点 最短路径问题，但是对于DAG，可以有更加简化的算法去计算，使得时间复杂度更低。
针对DAG的特点,以拓扑排序为基础,提出了解决DAG的最短路径问题的简单算法。通过理论分析,表明该算法具有理想的运算效率,其中,解决单源点问题的运算时间与E成正比,解决所有点对问题的运算时间与VE成正比。拓扑排序策略对于此类最短路径问题的研究,较传统的方法运算简单、求解直观。
针对DAG的特点,以拓扑排序为基础,提出了解决DAG的最短路径问题的简单算法。通过理论分析,表明该算法具有理想的运算效率,其中,解决单源点问题的运算时间与E成正比,解决所有点对问题的运算时间与VE成正比。拓扑排序策略对于此类最短路径问题的研究,较传统的方法运算简单、求解直观。
适用条件&范围
1. 单源最短路径(从源点s到其它所有顶点v);
2.有向无环图（DAG）
3.边权可正可负;
算法描述
（1）初始化，入度为0的节点d为0，其他的节点d值为INF。
（2）对DAG进行拓扑排序，得到拓扑序列。
（3）按照拓扑序列遍历DAG的点，进行松弛操作，对于每个点u，遍历其所有的出边<u,v>，如果d[v] > d[v] + length<u,v>，则更新。
时间复杂度
算法 时间复杂度O(V+E)。
Java代码实现
package algorithms;import util.AlgoGraph;/*** Created with IntelliJ IDEA.* Created by The_Sam on 2017/5/这篇关于算法导论——24.2 DAG最短路径算法java实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
