我正在写一篇关于一些图形算法(在 CPM 中使用)的论文，我需要一些可以找到 DAG 中所有关键路径的算法的名称。我看过 Floyd - Warshall 算法，我不知道它是否有助于找到 DAG 中的所有关键路径。如果关键路径和最长路径是同一件事，那么可以修改 Floyd - Warshall 算法，以找到图中所有最长而不是最短的路径。即使可以修改，是否有更好的方法找到所有关键路径？
最佳答案
为了找到一条关键路径，负权重的 Floyd--Warshall 明显不如以下民间传说(？)算法，该算法以线性时间计算从每个顶点开始的最长路径的长度。
for vertices v in topological order (sinks before sources):
set longest-path(v) := the maximum of 0 and length(v->w) + longest-path(w) for all arcs v->w
Floyd-Warshall 版本会在计算完距离后为所有顶点设置longest-path(v) := the maximum of -distance(v, w) > 数组。
要找到所有 的关键路径，计算longest-path 数组，并仅保留那些弧v->w 使得longest-path(v) = length(v->w) + longest-path(w)，使用递归枚举残差DAG中的所有路径。
关于algorithm - 是否有任何算法可以找到 DAG 中的所有关键路径？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18450062/