5

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

2 ответа 2

17

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

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

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

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

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

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

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

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

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

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

1
  • Спасибо. Теперь всё стало на свои места) 19 мая 2015 в 6:26
-2

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

3
  • Вроде бы Дейкстра работает для графов с ребрами отрицательных весов, но не для всех. Не уверен, вот и спросил) 18 мая 2015 в 21:01
  • 3
    мысль хорошая, но тогда цена пути будет зависеть не только от оригинальной цены ребер, но и от их количества. т.е. до операции стоимость двух путей может быть равна, например, 10+10=20 и -10+10+20 = 20. а после коррекции +10 - уже 20+20=40 и 0+20+30=50. и путь, например, 1+1+1+1+1+1 станет уже не кратчайшим.
    – user177221
    18 мая 2015 в 21:02
  • Достаточно интересно получается. Но не знаю, будет ли это работать на всех графах. 18 мая 2015 в 21:06

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.