通过根据其顶点的拓扑排序放宽加权DAG（有向无环图）G =（V, E）的边缘, 我们可以找出source（V + E）时间中来自单个源的最短路径。由于即使存在负权重边缘, 也不会存在负权重循环, 因此最短路径总是很好地描述。
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. do for each vertex v ∈ Adj [u]
5. do RELAX (u, v, w)该数据的运行时间由第1行和第3-5行的for循环确定。拓扑排序可以在∅（V + E）时间中实现。在第3-5行的for循环中, 就像Dijkstra的算法一样, 每个顶点有一个重复。对于每个顶点, 离开顶点的边都将被精确检查一次。与Dijkstra的算法不同, 我们每个边缘仅使用O（1）时间。因此, 运行时间为∅（V + E）, 在图表的邻接表描绘的大小上是线性的。
例：
步骤1：要对顶点进行拓扑排序, 请应用DFS（深度优先搜索）, 然后通过减小完成时间的顺序以线性顺序排列顶点。
现在, 按照拓扑排序的顺序获取每个顶点, 并放松每个边缘。
adj [s] →t, x
0 + 3 < ∞
d [t] ← 3
0 + 2 < ∞
d [x] ← 2
adj [t] → r, x
3 + 1 < ∞
d [r] ← 4
3 + 5 ≤ 2
adj [x] → y
2 - 3 < ∞
d [y] ← -1
adj [y] → r
-1 + 4 < 4
3 <4
d [r] ← 3
因此, 最短路径是：
s to x is 2
s to y is -1
s to t is 3
s to r is 3
