Самый длинный путь между всеми парами в DAG

Question

Я пытался найти самый длинный путь между всеми парами узлов в ациклическом ориентированном графе. Мой вопрос: будет ли Floyyd Warshall правильным ответом, если я сделаю следующее начальное условие в матрице смежности ?

1. Adj [I] [J] = 0, если I = J
2. Adj [I] [J] = - 1 * INF, если I = J, и не существует ребро между узлом I и J
!
3. Adj [I] [J] = ш [I] [J] в противном случае, где ш [I] [J] является вес ребра между узлом I и J

веса края может быть положительным и отрицательный.

Answer 1

Да, Floyd Warshall может дать правильный ответ на ваши проблемы, может быть доказан, как использовать Floyd Warshall, чтобы найти кратчайший путь между всеми парами в графе. Или вы можете умножить каждый ребро на (-1) и решить вашу проблему, например, найти кратчайший путь между всеми парами, а затем умножить свой результат на (-1).

Но вы можете сортировать граф топологически, а затем использовать динамическое программирование для вычисления, которое имеет сложность max (| E |, | V |) вместо | V |^3 FW.