Дейкстра за самый длинный путь в DAG

Question

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

Answer 1

Я думал о проблеме, и я думаю, что это вообще невозможно. Думаю, недостаточно быть ациклическим.

Например:

Мы хотим перейти от а к с в этом даге.

a - > b - > c
|           /\
v           |
d - - - - - 

d-c имеет длину 4

a-d имеет длину 1

все остальные имеют длину 2

Если вы просто замените функцию min на функцию max, алгоритм приведет к a-b-c, но самый длинный путь - a-d-c.

Я обнаружил два особых случая, когда вы можете использовать Дейкстру для вычисления самого длинного пути:

1. График является не только направленным ациклическим, но и ациклическим, если вы удалите направления. Другими словами: это дерево. Потому что в дереве самый длинный путь - это также самый короткий путь.
2. График имеет только отрицательные веса. Тогда вы можете использовать max вместо min, чтобы найти самый длинный путь. НО это работает, только если вес действительно отрицательный. Если вы просто инвертируете положительные веса, это не сработает.

Answer 2

Проблема наибольшего расстояния не имеет оптимальной подструктуры для любого графика , DAG или нет. Однако любая задача с самым длинным расстоянием на графе G эквивалентна задаче с наименьшим расстоянием в преобразованном графе G '= - G, то есть знак каждого веса ребра переворачивается.

Если ожидается, что преобразованный граф G 'будет иметь отрицательные ребра и циклы, то для определения кратчайшего расстояния используется алгоритм Беллмана-Форда. Однако, если G гарантированно будет иметь только неотрицательные веса (т.е. G '- неположительные веса), тогда алгоритм Дейкстры мог бы быть лучшим выбором по сравнению с Беллманом-Фордом. (см. ответ «Евгений Клюев» для графика - Дейкстра для длинного пути из одного источника ) Если G - DAG, то G 'также будет DAG. Для DAG у нас есть лучший алгоритм для нахождения кратчайшего расстояния, и его следует выбирать вместо Дейкстры или Беллмана-Форда.

Резюме:
Задача с самым длинным путем не имеет оптимальной подструктуры, поэтому изменение функции минимального веса в алгоритме Дейкстры на функцию максимального веса не будет работать для графа, будь то DAG или нет. Вместо того, чтобы модифицировать любой алгоритм кратчайшего пути (хорошо тривиальным образом), мы скорее преобразуем G, и посмотрим, какой алгоритм кратчайшего пути лучше всего работает на преобразованном G.

Примечание

     A-------B
     |       |              assume: edges A-B, B-C, C-A of same weight
     |       |
     +-------C

Мы видим MAX_DIS (A, B) = A-> C-> B
Для "MAX_DIS", чтобы быть оптимальной структурой, в приведенном выше случае соотношение

    MAX_DIS(A,B) = MAX_DIS(A,C) + MAX_DIS(C,B) should be satisfied.

Но это не так, как мы видим, MAX_DIS (A, C) = A-> B-> C и MAX_DIS (C, B) = C-> A-> B и, таким образом, это дает пример того, что проблема с самым длинным расстоянием может не иметь оптимальной подструктуры.

Answer 3

Существует три возможных способа применения Дейкстры, ни один из них не будет работать:
1. Непосредственно используйте операции «max» вместо операций «min».
2. Преобразуйте все положительные веса в отрицательные. Затем найдите кратчайший путь.
3. Дайте очень большое положительное число M. Если вес ребра равен w, теперь вместо W используется M-w. Затем найдите кратчайший путь.

Для DAG будет работать метод критического пути:
1: Найти топологический порядок.
2: Найдите критический путь.
см. [Horowitz 1995] E. Howowitz, S. Sahni и D. Metha, Основы структур данных в C ++, Computer Science Press, Нью-Йорк, 1995

Answer 4

Я предлагаю вам изменить алгоритм Дейкстры, чтобы он принимал инвертированное значение веса ребра.Поскольку график является ациклическим, алгоритм не будет входить в бесконечный цикл, используя отрицательные веса для дальнейшей оптимизации.Более того, теперь положительные веса становятся отрицательными, но опять-таки циклов нет.Это будет работать, даже если график имеет значение ненаправленный при условии, что вы не разрешите повторную вставку посещенных узлов (то есть остановите бесконечный переход между двумя узлами, потому что добавление отрицательного значения всегда будет лучше)

Answer 5

Единственное требование - не иметь отрицательных циклов.Если у вас нет циклов, то вы можете переназначить отрицательные, добавив наибольшее абсолютное значение из отрицательных весов ко всем весам.Таким образом, вы потеряете отрицательные веса, так как весь вес будет равен или больше нуля.Итак, подытожим, единственное, о чем нужно беспокоиться, это отсутствие отрицательного цикла.