Graph - Dijkstra для длинного пути с одним источником

Хорошо, я опубликовал этот вопрос из-за этого упражнения:

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

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

Хорошо, моя интуиция мне ответила:

Да, я думаю, он может быть изменен.

Я просто

инициализировать дистанционный массив до MININT
изменить distance[w] > distance[v]+weight на distance[w] < distance[v]+weight

Затем я провел некоторое исследование, чтобы проверить свой ответ. Я нашел этот пост:

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

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

Также в wiki алгоритм Bellman-Ford, он сказал правильно:

Алгоритм Беллмана-Форда вычисляет кратчайшие пути с одним источником в взвешенном орграфе. Для графов с только неотрицательными весами вершин, более быстрый алгоритм Дийкстры также решает проблему. Таким образом, Bellman-Ford используется в основном для графиков с отрицательным весом кромки.

Итак, я думаю, что мой ответ правильный, не так ли? Dijkstra действительно может быть проблемой с одним источником длинной траектории, и мои модификации также верны, верно?

Ответ 1

Нет, мы не можем ¹ - или, по крайней мере, никакая полиномиальная редукция/модификация не известна - самая длинная проблема пути NP-Hard, а dijkstra - в полиномиальное время!

Если мы можем найти modfication для dijsktra для ответа на проблему с длинным путём в полиномиальное время, мы можем получить P=NP

Если нет, укажите контрпример.

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

относительно изменения шага релаксации:

        A
       / \
      1   2
     /     \
    B<--1---C
edges are (A,B),(A,C),(C,B)

dijkstra из A сначала возьмет B, а затем B никогда не достигнет - потому что он выходит из набора distances.

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

(1) возможно, возможно, если P = NP это возможно, но это очень маловероятно.

Ответ 2

Да, мы можем. И ваш ответ почти прав. Кроме одного.

Вы принимаете отрицательные веса. В этом случае алгоритм Дейкстры не может найти самый длинный путь.

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

Ответ 3

Он работает в ориентированных ациклических графах, но не в циклических графах. Поскольку путь будет возвращаться, и нет способа избежать этого в dijkstra algo