Кратко о работе Дейкстры, ограничениях и альтернативы.
Как работает алгоритм Дейкстры (SSSP от источника s)
- Инициализация: для всех вершин $v$ положить $d[v]=+\infty$, $d[s]=0$, предок $\pi [v]=$ null.
- Поддерживать множество необработанных вершин и извлекать из него вершину $u$ с минимальным $d[u]$ (priority queue).
- Для каждой исходящей ребра $(u,v)$ выполнять операцию «расслабления»:
$$\text{если}d[u]+w(u,v)<d[v]\text{то}d[v]\leftarrow d[u]+w(u,v),\pi [v]\leftarrow u.$$ - Извлечённая вершина $u$ считается окончательно обработанной (её расстояние минимально и не изменится).
- Повторять до опустошения очереди. В конце $d[v]$ — длины кратчайших путей от $s$ (если достижимы).
Сложность (зависит от реализации очереди):
- с бинарной кучей: примерно $O((n+m)\log n)$ (часто сообщают $O(m\log n)$);
- с Fibonacci-кучей: $O(m+n\log n)$.
Ограничения применения
- Требование: все веса рёбер должны быть неотрицательными: $\forall (u,v)w(u,v)\ge 0$. Это критично для корректности (вытактовка «извлечённое минимальное расстояние окончательно» неверна при отрицательных весах).
- При наличии отрицательных циклов задача «кратчайшего пути» не имеет смысла (пути можно бесконечно уменьшать).
- Подходит для одноисточниковых задач; для всех пар можно запускать многократно или использовать другие алгоритмы.
Альтернативы при отрицательных весах
- Bellman–Ford: корректен при отрицательных рёбрах, обнаруживает отрицательные циклы; сложность $O(nm)$.
- SPFA (очередь релаксаций): на практике часто быстрее, но худший случай плохой (вплоть до экспоненциального/псевдополиномиального поведения); не рекомендуется как строгая гарантия.
- Johnson для всех пар: сначала Bellman–Ford для получения потенциалов, затем пере-ребалансировка весов и запуск Dijkstra из каждой вершины; подходит когда есть отрицательные рёбра, но нет отрицательных циклов. Сложность: $O(nm+n\cdot T_{Dijkstra})$.
- Floyd–Warshall: динамическое программирование для всех пар, работает с отрицательными весами (без отрицательных циклов), сложность $O(n^3)$.
Альтернативы/подходы для динамически меняющейся структуры графа
- Пересчёт по требованию: при небольшом числе изменений просто перезапускать Dijkstra/Bellman–Ford (часто прост и практичен).
- Инкрементные/декрементные динамические алгоритмы (теоретические): Even–Shiloach (для неотрицательных или невзвешенных графов, преимущественно декрементальные), Ramalingam–Reps, Demetrescu–Italiano (полностью динамические алгоритмы для APSP) — дают лучшие амортизированные времена, но сложны в реализации и с большими константами.
- Алгоритмы для маршрутизации/запросов (практически для дорожных сетей): A* (с эвристикой), Contraction Hierarchies (CH), Customizable Route Planning (CRP) — позволяют быстро отвечать на запросы и поддерживать частичные обновления весов (CRP лучше подходит для частых изменений весов).
- При небольших локальных изменений можно поддерживать дерево кратчайших путей и выполнять локальные обновления релаксациями (algorithms для поддержания SPT), либо поддерживать расстояния приближённо (approximate dynamic SSSP).
Рекомендации практические
- Если веса неотрицательны: используйте Dijkstra с подходящей кучей (binary или Fibonacci / pairing heap).
- Если возможны отрицательные ребра, но нет отрицательных циклов: Bellman–Ford (для одного источника) или Johnson (для всех пар).
- Для частых быстрых запросов в больших дорожных графах с динамическими весами — рассмотреть CH/CRP/A* и механизмы частичного обновления; для теоретически строгих динамических задач — искать специализированные динамические SSSP/APS-программы (Even–Shiloach, Demetrescu–Italiano и др.).
Если нужно, могу привести псевдокод Дейкстры, пример работы или сравнение сложностей конкретных алгоритмов.