Как вычислить критический путь направленного ациклического графа?

Question

Каков наилучший (в отношении производительности) способ вычисления критического пути направленного ациклического графа, когда узлы графа имеют вес?

Например, если у меня следующая структура:

            Node A (weight 3)
               /            \
     Node B (weight 4)      Node D (weight 7)
     /               \
Node E (weight 2)   Node F (weight 3)

Критический путь должен быть A-> B-> F (общий вес: 10)

Answer 1

Я бы решил это с помощью динамического программирования. Чтобы найти максимальную стоимость от S до T:

• Топологически сортируйте узлы графа как S = x_0, x_1, ..., x_n = T. (Игнорируйте любые узлы, которые могут достигнуть S или быть достигнуты из T.)
• Максимальная стоимость от S до S - это вес S.
• Предполагая, что вы рассчитали максимальную стоимость от S до x_i для всех i

Answer 2

Есть статья, в которой предполагается использовать алгоритм для этого: «Критический путь в сети активности с ограничениями по времени». К сожалению, я не смог найти ссылку на бесплатную копию. Если не считать этого, я могу только поддержать идею модификации http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm или http://en.wikipedia.org/wiki/A*

ОБНОВЛЕНИЕ: Я прошу прощения за дерьмовое форматирование - механизм уценки на стороне сервера явно сломан.

Answer 3

Я понятия не имею о "критических путях", но я предполагаю, что вы имеете в виду это .

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

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

Но ничто действительно не спасет вас от полного обхода, если вы этого не сделаете. Порядок на самом деле не имеет значения, если вы делаете обход и никогда не идете по одному и тому же пути дважды.

Answer 4

Мой первый ответ, так что прошу прощения за любые нестандартные вещи в культуре stackoverflow.

Я думаю, что решение простое. Просто отмените веса и запустите классический кратчайший путь для DAG (конечно, модифицированный для весов вершин). Это должно бежать довольно быстро. (Временная сложность O (V + E) может быть)

Я думаю, что это должно сработать, так как когда вы уменьшите вес, самый большой из них станет наименьшим, второй по величине будет вторым наименьшим и так далее, как если бы a > b затем -a < -b. Тогда достаточно запустить DAG, поскольку он найдет решение для наименьшего пути отрицательного и, таким образом, найдет самый длинный путь для исходного

Answer 5

Попробуйте метод A *.

A * Алгоритм поиска

В конце концов, чтобы разобраться с листьями, просто заставьте их всех привести к конечной точке, чтобы установить в качестве цели.