Что такое потенциалы Джонсона и зачем они для всех пар с отрицательными рёбрами?
Нужны кратчайшие пути между всеми парами, но граф разреженный и есть отрицательные рёбра. Флойд O(V³) слишком медленный для моего V, а Дейкстру нельзя из-за минусов. Говорят, алгоритм Джонсона решает это через «потенциалы». Объясните идею (без полной реализации, просто как это работает).
2 ответа
Идея Джонсона — перевесить рёбра так, чтобы все веса стали неотрицательными, не изменив кратчайшие пути, и тогда запустить быструю Дейкстру из каждой вершины.
Шаги:
- Добавляем фиктивную вершину
q, соединённую рёбрами веса 0 со всеми вершинами. - Запускаем Беллман-Форд из
q— получаем потенциалыh[v](кратчайшее расстояние отqдоv). Заодно ловим отрицательный цикл — если он есть, ответа нет. - Перевешиваем каждое ребро:
w'(u,v) = w(u,v) + h[u] − h[v]. По свойству потенциаловw' >= 0всегда (это неравенство треугольникаh[v] <= h[u] + w(u,v)). - Запускаем Дейкстру из каждой вершины по новым весам, затем восстанавливаем настоящее расстояние:
dist(u,v) = dist'(u,v) − h[u] + h[v].
Сложность O(V·E·log V) (одна Дейкстра O(E log V), их V штук) + один Беллман-Форд O(V·E). На разреженных графах это сильно быстрее Флойда O(V³).
Почему перевешивание не меняет кратчайшие пути: для любого пути v0 → v1 → ... → vk сумма новых весов телескопически сворачивается до (старая сумма) + h[v0] − h[vk]. Слагаемое h[v0] − h[vk] зависит только от концов, а не от маршрута — значит порядок путей по длине сохраняется, минимальный остаётся минимальным. Это и есть ключевая магия потенциалов (та же идея — в min-cost-max-flow).