一，DAG算法的思想
根据结点的拓扑排序次序来对带权重的有向无环图G进行边的松弛操作，在有向无环图中，边可以为负值但是没有权重为负值的环，因此最短路都是存在的。
二，DAG算法介绍
准备阶段：一副赋值有向无环图
算法过程：对图G中的结点进行拓扑排序就，使所有结点线性排列，然后按照拓扑排序的次序对每个结点发出的所有边进行松弛操作。
三，DAG伪代码
DAG_SHORTEST_PATHS(G,w,s)
1. topologically sort the vertices of G
2. INITIALIZE_SINGLE_SOURCE(G,s)
3. for each vertex u,taken in topologically sorted order
4. for each vertex v∈G.Adj[u]
5. RELAX(u,v,w)
第1行对图G进行拓扑排序；第2行对所有结点进行初始化；第3-5行，按照拓扑排序的顺序对每个结点到其各邻结点的边进行松弛
以书上的例子为例，图a中，各结点已经按照拓扑排序线性线性排列并已初始化；图b中，我们开始松弛第一个结点r，由于r.d=∞，因此他的邻结点s、t都不需要更新；图c中
版权声明：本文为qq_41773240原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。