通过根据其顶点的拓扑排序放宽加权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, x0 + 3 <
∞d [t] ← 30 + 2 <
∞d [x] ← 2
文章图片
adj [t] → r, x3 + 1 <
∞d [r] ← 43 + 5 ≤ 2
文章图片
adj [x] → y2 - 3 <
∞d [y] ← -1
文章图片
adj [y] → r-1 + 4 <
43 <
4d [r] ← 3
文章图片
因此, 最短路径是：
s to x is 2s to y is -1s to t is 3s to r is 3推荐阅读
- 图论算法（全对最短路径）
- 最短路径（ellman-Ford算法）
- 图论算法（Dijkstra算法）
- 图论（松弛技术）
- 图论（最短路径的表示）
- 图论（负权重边）
- 图论（单源最短路径）
- DNS问题故障排除（使用nslookup、dig和host等命令）
- MySQL性能调优和优化技巧（如何优化数据库（））