#Kahn 算法

DAG 上的最短路径问题

DAG 即有向无环图，DAG 上的最短路径先对图做拓扑排序，按照拓扑序列依次取出每个顶点，对它的所有出边执行松弛操作即可求出单源最短路径；该算法可以处理负权边，不能处理负环（DAG 本身不存在环），时间复杂度 O(n+m)，效率优于 Bellman‑Ford 与 SPFA。