Почему Дейкстра не работает с отрицательными рёбрами? Дайте контрпример
Все говорят «Дейкстра не работает при отрицательных весах», но в учебнике не вижу почему — алгоритм же всё равно отрабатывает и что-то выдаёт. Можете показать конкретный маленький граф, где Дейкстра даёт неправильный ответ?
2 ответа
Дейкстра жадно фиксирует вершину как «готовую» и больше её не трогает. Это корректно, только если добавление рёбер не уменьшает расстояние — то есть веса неотрицательны. Отрицательное ребро может «удешевить» путь к уже зафиксированной вершине, но алгоритм её уже закрыл.
Контрпример (3 вершины, рёбра):
A -> B : вес 2
A -> C : вес 5
B -> C : вес -10
Ищем кратчайший путь из A. Дейкстра берёт B (dist=2), потом видит C через B: 2 + (-10) = -8. Но порядок извлечения из кучи: сначала B (2), при релаксации C получает -8, кладём в кучу. Затем извлекаем C=-8 — тут как раз сработает. Чтобы сломать наверняка, нужно, чтобы вершина закрылась РАНЬШЕ, чем придёт дешёвое отрицательное ребро:
A -> B : 1
A -> C : 2
C -> B : -3
Дейкстра извлекает B (dist=1) и фиксирует его. Потом извлекает C (dist=2), релаксирует B: 2 + (-3) = -1 < 1. Но B уже закрыт — и если бы из B шли рёбра дальше, они посчитались бы со старым значением 1, а не -1. Правильный ответ dist[B] = -1, Дейкстра даёт 1.
Для отрицательных рёбер нужен Беллман-Форд (O(VE)) или Джонсон для всех пар.
Нюанс: на DAG или на графе, где отрицательное ребро не создаёт «обхода» к уже закрытой вершине, Дейкстра иногда случайно даёт верный ответ — поэтому на слабых тестах «вроде работает». Не полагайтесь на это. Инвариант корректности Дейкстры — «расстояние извлекаемой вершины финально» — держится строго при w >= 0. Любое отрицательное ребро его ломает в общем случае.