график -Дейкстры для единственного -Самый длинный путь к источнику
Хорошо, я задал этот вопрос из-за этого упражнения:
Можем ли мы изменить алгоритм Дейкстры, чтобы решить проблему с одним источником -о самом длинном пути, заменив минимум на максимум? Если да, то докажите, что ваш алгоритм верен. Если нет, то приведите контрпример.
Для этого упражнения или всего, что связано с алгоритмом Дейкстры, я предполагаю, что в графе нет отрицательных весов . В противном случае это не имеет особого смысла, так как даже для задачи о кратчайшем пути Дейкстра не может работать должным образом, если существует отрицательное ребро.
Хорошо, моя интуиция ответила за меня:
Да, я думаю, что это можно изменить.
Я просто
- инициализирую массив расстояний до MININT
- меняю
distance[w] > distance[v]+weightнаdistance[w] < distance[v]+weight
Затем я провел небольшое исследование, чтобы проверить свой ответ. Я нашел это сообщение:
Самый длинный путь между источником и определенными узлами в DAG
Сначала я подумал, что мой ответ был неправильным из-за сообщения выше. Но я обнаружил, что, возможно, ответ в посте выше неверен. Он перепутал задачу с одним источником -о самом длинном пути с задачей о самом длинном пути .
Также в вики Алгоритм Беллмана-Форда правильно сказано:
Алгоритм Беллмана-Форда вычисляет одиночные -исходные кратчайшие пути во взвешенном орграфе. Для графов только с не -отрицательными весами ребер более быстрый алгоритм Дейкстры также решает проблему . Таким образом, Беллман-Форд используется в основном для графов с отрицательными весами ребер.
Итак, я думаю, что мой ответ правильный, верно? Дейкстра действительно может быть Единственным -Источником Задачей о самом длинном пути, и мои модификации тоже верны, верно?