Поиск кратчайшего пути от одной вершины (SSSP)

1 Постановка задачи

Пусть задан граф $G = (V, E)$ с весами рёбер $f(e)$ и выделенной вершиной-источником $u$. Последовательность $P(u, v)$ рёбер $e_1 = (u, w_1)$, $e_2 = (w_1, w_2)$, …, $e_k = (w_{k-1}, v)$ называется путём, идущим от вершины $u$ к вершине $v$. Суммарный вес этого пути равен

$f(P(u, v)) = \sum_{i = 1}^k f(e_i).$

Требуется для каждой вершины $v$, достижимой из вершины-источника $u$, указать путь $P^*(u, v)$, имеющий наименьший возможный суммарный вес:

$f(P^*(u, v)) = \min f(P(u, v)).$

2 Варианты задачи

Задача может быть поставлена как для ориентированного, так и для неориентированного графа. Приведённая постановка задачи применима в обоих случаях.

В зависимости от ограничений на возможные значения весов различают следующие случаи.

• Единичные веса. В этом случае задача существенно упрощается и может быть решена за линейное время алгоритмом поиска вширь.
• Положительные целые веса. Задача также может быть решена за линейное время (хотя и с большей константой).
• Неотрицательные веса. Часто встречающееся на практике ограничение, когда вес ребра соответствует времени или стоимости прохождения участка маршрута и не может быть отрицательным.
• Произвольные веса. Наиболее общая постановка. Граф не должен содержать циклов с отрицательным суммарным весом, иначе кратчайшего пути не существует.

3 Свойства задачи

Решение задачи удовлетворяет принципу оптимальности: если путь $P^*(u, w)$ является частью кратчайшего пути $P^*(u, v)$, то $P^*(u, w)$ является кратчайшим путём от источника $u$ до вершины $w$.

Принцип оптимальности означает, что для каждой вершины $v$ вместо всего кратчайшего пути $P^*(u, v)$ достаточно хранить его последнее ребро $e^*_v$. Кратчайший путь от $u$ к $v$ может быть восстановлен за время $O(\left |P^*(u, v) \right |)$, если, начиная с вершины $v$, проходить рёбра $e^*_w$ в обратном направлении до тех пор, пока не будет посещена вершина $u$.

4 Описание входных и выходных данных

Входные данные: взвешенный граф $(V, E, W)$ ($n$ вершин $v_i$ и $m$ рёбер $e_j = (v^{(1)}_{j}, v^{(2)}_{j})$ с весами $f_j$), вершина-источник $u$.

Объём входных данных: $O(m + n)$.

Выходные данные: для каждой вершины $v$ исходного графа – последнее ребро $e^*_v = (w, v)$, лежащее на кратчайшем пути от вершины $u$ к $v$.

Объём выходных данных: $O(n)$.

5 Алгоритмы решения задачи

• 'Поиск в ширину (BFS) для ориентированных невзвешенных графов, сложность $O(m)$.
• 'Алгоритм Дейкстры для ориентированных графов с неотрицательными весами, сложность $O(m + n \ln n)$.
• Алгоритм Беллмана-Форда для ориентированных графов с произвольными весами, сложность $O(mn)$.
• Алгоритм Δ-шагания для ориентированных графов с неотрицательными весами, средняя сложность на графах со случайными весами $O(n + m + dL)$, параллельная сложность $O((dL + \ln n) \ln n$ со средней работой $O(n + m + dL \ln n)$.
• Алгоритм Торупа представляет собой теоретическое доказательство возможности решения задачи для неориентированных графов с положительными целыми весами за линейное время $O(m)$.

Обозначения: $m$ – число рёбер, $n$ – число вершин, $d$ – максимальная степень вершины, $L$ – максимальный суммарный вес кратчайшего пути.