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

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

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

[math]\displaystyle{ f(P(u, v)) = \sum_{i = 1}^k f(e_i). }[/math]

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

[math]\displaystyle{ f(P^*(u, v)) = \min f(P(u, v)). }[/math]

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

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

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

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

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

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

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

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

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

Объём входных данных: [math]\displaystyle{ O(m + n) }[/math].

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

Объём выходных данных: [math]\displaystyle{ O(n) }[/math].

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

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

Обозначения: [math]\displaystyle{ m }[/math] – число рёбер, [math]\displaystyle{ n }[/math] – число вершин, [math]\displaystyle{ d }[/math] – максимальная степень вершины, [math]\displaystyle{ L }[/math] – максимальный суммарный вес кратчайшего пути.