有向无环图中的单源最短路径

通过根据其顶点的拓扑排序放宽加权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