Есть ли алгоритм, который может найти все критические пути в DAG?

Это можно сделать с помощью Floyd Warshall, просто инвертируя все веса (поскольку это DAG, отрицательных циклов не будет). Однако Floyd Warshall — это O(n^3), в то время как существует более быстрый алгоритм линейного времени.

Из Википедии

Самый длинный путь между двумя заданными вершинами s и t во взвешенном графе G — это то же самое, что и кратчайший путь в графе −G, полученном из G путем замены каждого веса на его отрицание. Следовательно, если кратчайшие пути можно найти в −G, то и самые длинные пути можно найти в G.[4] Для большинства графов это преобразование бесполезно, поскольку оно создает циклы отрицательной длины в −G. Но если G является ориентированным ациклическим графом, то нельзя создавать отрицательные циклы, а самые длинные пути в G можно найти за линейное время, применяя алгоритм линейного времени для поиска кратчайших путей в −G, который также является ориентированным ациклическим графом. 4] Например, для каждой вершины v в данной DAG длина самого длинного пути, заканчивающегося в v, может быть получена с помощью следующих шагов:

Найдите топологический порядок данного DAG. Для каждой вершины v группы DAG в топологическом порядке вычислите длину самого длинного пути, заканчивающегося в v, просматривая ее входящие соседи и добавляя единицу к максимальной длине, зарегистрированной для этих соседей. Если у v нет входящих соседей, установите длину самого длинного пути, заканчивающегося в v, равной нулю. В любом случае запишите этот номер, чтобы последующие шаги алгоритма могли получить к нему доступ.

Как только это будет сделано, самый длинный путь во всем DAG можно получить, начав с вершины v с наибольшим записанным значением, затем неоднократно возвращаясь назад к входящему соседу с наибольшим записанным значением и обращая последовательность вершин, найденных в Сюда.

Обратите внимание, что поиск всех самых длинных путей более проблематичен, поскольку их может быть экспоненциально большое количество. Следовательно, не существует эффективного способа перечислить их все в худшем случае, хотя их можно легко перечислить или представить неявно.

Для нахождения одного критического пути алгоритм Флойда--Уоршалла с минусовыми весами заметно уступает следующему народному (?) алгоритму, который за линейное время вычисляет длину самого длинного пути из каждой вершины.

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) for all vertices w после вычисления массива distance.

Чтобы найти все критические пути, вычислите массив longest-path и, сохранив только те дуги v->w, что longest-path(v) = length(v->w) + longest-path(w), перечислите все пути в остаточной DAG, используя рекурсию.