Коротко об алгоритме, затем — влияние отрицательных весов и масштаб до миллиардов вершин.
1) Суть Dijkstra
- Назначение: однопарный кратчайший путь от источника в взвешенном ориентированном/неориентированном графе при неотрицательных весах.
- Идея: в каждом шаге извлекается вершина с минимальным расстоянием (жадно «фиксируется»), затем релаксируются исходящие рёбра.
- Типичная реализация и асимптотика:
- с двоичной кучей: $\mathcal{O}((V+E)\log V)$, обычно пишут $\mathcal{O}(E\log V)$ для связных графов;
- с кучей Фибоначчи: $\mathcal{O}(V\log V+E)$;
- простой массив/матрица смежности: $\mathcal{O}(V^2)$.
- Память: хранение графа $\mathcal{O}(V+E)$ (например CSR/adj-list).
2) Отрицательные веса
- Требование: Dijkstra корректен только при неотрицательных весах. Причина — жадный выбор может зафиксировать вершину с неокончательным значением, если позже появится путь с отрицательной суммой.
- Простой контрпример: вершины $A,B,C$, рёбра $A\to B$ вес $2$, $A\to C$ вес $5$, $B\to C$ вес $-4$. Кратчайший путь $A\to B\to C$ имеет длину $-2$, но Dijkstra сначала зафиксирует $C$ с меткой $5$ — неверно.
- Если присутствуют отрицательные рёбра:
- при отсутствии отрицательных циклов используйте Bellman–Ford: сложность $\mathcal{O}(V\cdot E)$ (детектирует отрицательные циклы);
- практические ускорения: SPFA (queue-based), но у неё худший случай экспоненциальный/квадратичный;
- для всех-пар кратчайших путей: алгоритм Johnson — сначала Bellman–Ford ($\mathcal{O}(VE)$) для вычисления потенциалов, затем $V$ запусков Dijkstra — суммарно $\mathcal{O}(VE+V\cdot E\log V)$ при использовании кучи.
- Если в графе есть отрицательные циклы, понятие кратчайшего пути в обычном смысле не определено (можно убывать в $-\infty$).
3) Граф с миллиардами вершин ($V\sim 10^9$)
- Проблемы с применением классического Dijkstra на одной машине:
- память: при средней степени $k$ число рёбер $E\approx kV$. Для $V=10^9$, $k=10$ получаем $E\approx 10^{10}$. Даже при $b=16$ байт на ребро память $\approx bE=1.6\cdot 10^{11}$ байт $\approx 160$ ГБ только на рёбра — плюс структура для расстояний ($V$ записей) — многомашинно.
- время: даже алгоритм $\mathcal{O}(E\log V)$ даст огромную константу и долго выполняется.
- Практические подходы при больших графах:
- распределённые/внешнемемориальные реализации: Pregel/Giraph/GraphX, а также хранение в SSD/RAID; алгоритмы с минимизацией I/O; требования — масштабируемая кластерная инфраструктура.
- параллельные версии и алгоритмы: $\Delta$-stepping (параллельно, требует неотрицательных весов), распределённый Bellman–Ford для отрицательных весов (медленнее).
- для многократных запросов: предварительная обработка — Contraction Hierarchies, ALT (landmarks), многослойные сокращения; дают очень быстрые запросы, но требуют дополнительных ресурсов для предобработки и корректны при неотрицательных весах.
- для одиночного запроса s→t: bidirectional Dijkstra, A* (если есть эвристика), многопоточность и раннее прекращение.
- приближённые/сэмплирующие методы и sketch-структуры для упрощённых ответов.
- Выводы по применимости:
- если есть отрицательные веса → Dijkstra обычно неприменим; используйте Bellman–Ford / Johnson / SPFA в зависимости от задачи;
- если граф миллиардный и веса неотрицательны → на одной машине Dijkstra обычно невозможен; применяйте распределённые/внешнемемориальные/параллельные алгоритмы ($\Delta$-stepping, Pregel-подходы) или методы с предобработкой (CH, ALT) для многократных запросов;
- если отрицательные веса и миллиард вершин → задача требует распределённого Bellman–Ford/итеративной релаксации или переработки модели (элиминация отрицательных рёбер, переопределение весов), но производительность сильно страдает.
Краткая рекомендация: для корректности — сначала проверить наличие отрицательных рёбер/циклов; для масштаба — проектировать хранение и вычисление распределённо, выбирать параллельные или приближённые методы и/или предобработку в зависимости от характера запросов (одиночные vs множество).