Кратко, по делу — анализ, модификации и практические устойчивые подходы для маршрутизации в графах с отрицательными ребрами и меняющимися весами.
1) Dijkstra — суть и ограничение
- Алгоритм: жадно расширяет вершины по возрастанию расстояний; релаксация: $d(v)\leftarrow \min (d(v),d(u)+w(u,v))$.
- Сложность (с кучей): $O(m+n\log n)$ или $O((n+m)\log n)$ в зависимости от реализации.
- Ограничение: работает только при неотрицательных весах. При наличии отрицательных ребер результирующие метки могут быть некорректны.
2) Графы с отрицательными ребрами (без отрицательных циклов)
- Bellman–Ford: однопроходный алгоритм, выдерживает отрицательные веса; релаксация выполняется $(n-1)$ раз, сложность $O(nm)$. Позволяет также обнаружить отрицательный цикл (если на $(n)$-й итерации есть улучшение).
- Johnson: для APSP на графах с отрицательными ребрами, но без отрицательных циклов:
- вычислить потенциалы $\pi (v)$ с помощью Bellman–Ford от добавленной фиктивной вершины;
- переопределить веса $w^{\prime }(u,v)=w(u,v)+\pi (u)-\pi (v)$ (все неотрицательны);
- запуск Dijkstra из каждой вершины по $w^{\prime }$ и обратно восстановление расстояний.
- Если есть отрицательные циклы — их нужно сначала обнаружить и обработать (например, задать политики: запрещать такие маршруты, метить области как «неопределённые»).
3) Динамические изменения весов — классификация и алгоритмы
- Типы изменений: увеличение веса, уменьшение веса, вставка/удаление ребра/вершины.
- Подходы:
- Полная перерасчётка (реинитация Dijkstra/Bellman–Ford) — прост, но дорого при частых изменениях.
- Инкрементальные/декрементальные алгоритмы (динамические SSSP/APSP):
- Ramalingam–Reps — обновление шортест-пассов при локальных изменениях (часто значительно быстрее полного пересчёта).
- Even–Shiloach (ES-tree) — эффективен для декрементальных изменений в неотрицательных графах (вечный источник, суммарная сложность зависит от суммарного снижения расстояний).
- Fully-dynamic APSP (Demetrescu–Italiano и др.) — сложные структуры с высокими константами, применимы при жёстких требованиях к латентности.
- Replacement paths и distance sensitivity oracles — предобработка для быстрого ответа на запросы «кратчайший путь при удалении ребра/вершины» (гарантированно быстрые ответы, но дорога предобработка).
- Warm-started Dijkstra / A* — при малых локальных изменениях начать поиск с ранее вычисленных меток и использовать эвристику (ALT), чтобы сильно сократить просмотр.
4) Практические устойчивые решения для реального времени
- Правила выбора:
- Если веса могут быть отрицательными, но нет отрицательных циклов: разово вычислить потенциалы (Bellman–Ford) и потом использовать Dijkstra по переопределённым весам.
- Для частых динамических изменений на больших дорожных графах: использовать иерархические методы с дешёвой кастомизацией:
- Contraction Hierarchies (CH) + Customization (CCH), Customizable Route Planning (CRP) — дорогая предобработка структуры, но быстрая «кастомизация» при изменении весов.
- Transit Node Routing / Hub labeling / CH комбинируют предобработку и дают миллисекундные ответы.
- Для сетей с требованиями к устойчивости: хранить несколько альтернатив (k‑shortest): $k$-shortest paths, ECMP (эквивалентные многопутевые) и заранее предсчитать резервные сегменты (replacement paths).
- Для времезависимых (time-dependent) графов — использовать модифицированный Dijkstra/A* с функциями времени на ребрах и требованием FIFO; эвристики ALT остаются применимы.
- Устойчивость/отказоустойчивость:
- Предобработка sensitivity-oracles / replacement-paths для быстрых ответов при отказе рёбер.
- Мультипутьный маршрут (разделение трафика) и резервные пути уменьшают необходимость немедленного пересчёта.
- Локальное восстановление (local repair): при изменении веса пересчитывать только компоненту, на которую влияет изменение (используя очередь релаксаций из изменённых вершин).
- Пороговые политики: игнорировать малые флуктуации весов, обновлять маршрут только при значимых изменениях (экономия вычислений, стабилизация).
- Параллелизация: распределённый/параллельный Dijkstra, GPU-реализации и многопоточность для снижения латентности при полном пересчёте.
5) Практическая рецептура (что использовать в зависимости от ситуации)
- Небольшие графы или редкие изменения, возможны отрицательные ребра:
- Bellman–Ford или Johnson + Dijkstra (если нужен APSP).
- Большие дорожные сети, частые изменения весов (например, live трафик):
- Contraction Hierarchies / CCH / CRP + быстрая кастомизация весов; хранить k‑альтернативы; warm-started queries.
- Очень частые мелкие обновления:
- Инкрементальные алгоритмы (Ramalingam–Reps, ES-tree), локальные обновления и threshold-политики.
- Требуется высокая отказоустойчивость:
- Distance sensitivity oracles / replacement-paths, мультипутьная маршрутизация, подготовленные резервные сегменты.
6) Замечания по реализации и качество
- Проверяйте наличие отрицательных циклов (Bellman–Ford) — иначе расстояния бессмысленны.
- Эвристики (ALT: landmarks) и потенциалы ускоряют поиск, но корректность требует неотрицательных переработанных весов.
- В реальном времени комбинируйте: предобработку (для ускорения) + быстрые локальные обновления + политики игнорирования шумовых изменений.
Если нужно, могу дать конкретные библиотеки/реализации (C++, Python) и конкретные параметры для CH/CRP/ALT или псевдокод для Ramalingam–Reps / warm-start Dijkstra.