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

#алгоритм #графы

Сидел, читал про алгоритм Дейкстры и Форда-Беллмана. В определении данных алгоритмов
есть условие - всё веса рёбер должны быть больше, либо равны нулю. Объяснения не нашел.
Почему накладывается такое условие?
    

Ответы

Ответ 1

На самом деле все по-другому.

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

Но в графе с отрицательными дугами это не так! Рассмотрим такой вот граф, заданный
матрицей смежности:

+---+---+---+---+
|   | А | Б | В |
+---+---+---+---+
| А |   | 4 | 2 |
+---+---+---+---+
| Б |   |   |-3 |
+---+---+---+---+
| В |   |   |   |
+---+---+---+---+


Запустим алгоритм Дейкстры из вершины А. На первом шаге у нас будут расстояния до
вершин Б и В - 4 и 2 соответственно, поэтому алгоритм решит, что уже нашел кратчайший
путь к вершине В - ведь кратчайший путь к В никак не может идти через Б, не так ли?
С сожалению, не так - очевидно, путь А-Б-В на самом деле короче чем А-В.

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

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

Просто потому что понятие "кратчайший путь" в таких графах не определено. Всегда
можно пройтись по отрицательному циклу еще один раз - и получить еще более короткий путь.

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

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


Ответ 2

А вообще я так прикинул, пусть есть отрицательные веса. Найдем ребро e с наименьшим
весом (то есть ребро с отрицательным весом максимального модуля). тогда w(e) = -n,
где n > 0. Сместим все веса на n. Запускаем алгоритм (он теперь отработает на корректных
данных) и вычитаем сколько "лишнего накручено". Или бред написал?)