Кратчайшие пути для всех пар вершин

В этой главе мы займёмся задачей о нахождении кратчайших путей для всех пар вершин графа. Таблица расстояний между всевозможными парами городов в атласе дорог получается в результате решения именно такой задачи. Как и в главе 25, будем рассматривать ориентированный взвешенный граф G = (V, Е) с вещественной весовой функцией w: Е -> KL Для каждой пары вершин и, v G V мы должны найти кратчайший путь и в v, точнее, путь наименьшей длины (длина пути определяется как сумма весов всех его рёбер). Таким образом, ответом в задаче о кратчайших путях можно считать таблицу, в которой на пересечении строки и и столбца v которой находится вес кратчайшего пути из и в v (дополненную некоторой информацией о самих этих путях, см. ниже).

Разумеется, можно решить эту задачу, если \V\ раз применить алгоритм для поиска кратчайших путей из одной вершины (ко всем вершинам графа по очереди). Если все ребра графа имеют неотрицательные веса, то разумно использовать алгоритм Дейкстры; при простой реализации очереди с приоритетами с помощью массива общее время работы алгоритма составит 0(V3 + VE) = 0(V3).

Если очередь реализовать с помощью двоичной кучи, то общая стоимость составит 0(VElgV), что даёт выигрыш для разреженных графов. Обе эти оценки можно улучшить, использовав фибоначчиевы кучи, для которых общее время работы алгоритма есть алгоритма будет О (V2 lg V + VE).

Если в графе есть рёбра с отрицательными весами, то алгоритм Дейкстры применить нельзя. Если вместо него использовать более медленный алгоритм Беллмана-Форда, выполняя его для каждой вершины графа, общее время работы составит 0(V2E) - для плотных графах это будет 0(V4). Алгоритмы, описанные ниже, работают быстрее. Кроме того, в этой главе мы установим связь между задачей о нахождении кратчайших путей для всех пар вершин графа и умножением матриц, а также исследуем ее алгебраическую структуру.

В большинстве алгоритмов этой главы графы представляются матрицами смежности. Исключением является алгоритм Джонсо-

на для разреженных графов, который (как и алгоритмы поиска из одной вершины) использует списки смежности. Естественно сочетать сведения о наличии ребра и о его весе в одной матрице, полагая веса отсутствующих рёбер бесконечными.

Таким образом, при обработке взвешенного ориентированного графа G = (V, Е) алгоритму даётся матрица W = (?%•), где

{Оесли г = j,

вес (ориентированного) ребраесли гф j и£ Е,

ооесли гф j и$ Е.

(26.1)

Ребра могут иметь отрицательный вес. Мы будем, однако, предполагать, что циклов отрицательного веса в графе нет.

Представленные в данной главе алгоритмы нахождения кратчайших путей для всех пар вершин будут вычислять матрицу D = (dij) размером га X га, элемент dij которой содержит вес кратчайшего пути из вершины г в вершину j, то есть равен S(i,j) в обозначениях предыдущей главы.

Решение задачи о кратчайших путях для всех пар вершин должно включать в себя не только веса кратчайших путей, но и матрицу предшествования (predecessor matrix) П = (7r8j), в которой 7r8j является вершиной, предшествующей j на одном из кратчайших путей из г в j. (мы полагаем 7r8j = nil, если г = j или путей из г в j не существует). Для каждой вершины г £ V можно определить подграф предшествования (predecessor subgraph) GVti = (VVti, EVti), где

K,i = {j eV : mj ф nil} U {г},

и

En,i = j £ K,i и 7Tij ф nil}.

Мы будем требовать, чтобы для каждого г подграф предшествования GVti был деревом кратчайших путей из вершины г (в смысле главы 25). В этом случае следующая процедура печатает кратчайший путь из вершины г в вершину j.

{\sc Print-All-Pairs-Shortest-Path>$(\Pi,i,j)$\\

1if $i=j$

2then print $i$

3else if $\pi {ij}=\mbox{\sc nil}$

4then print "Пути из" $i$ "в" $j$ нет

5else {\sc Print-All-Pairs-Shortest-Path>$(\Pi,i,\pi {ij»$

6print $j$

Мы не будем подробно говорить о построении матрицы предшествования (её свойствам посвящено несколько упражнений). План главы

В разделе 26.1 рассматривается алгоритм решения задачи о кратчайших расстояниях для всех пар вершин, в основе которого лежит умножение матриц. Время работы этого алгоритма - 0(V3lgV); он вычисляет степень матрицы, многократно возводя её в квадрат.

Более быстрый (0(V3)) алгоритм Флойда-Уоршолла, также использующий технику динамического программирования, излагается в разделе 26.2. В этом же разделе рассматривается задача о транзитивном замыкании ориентированного графа, которая оказывается тесно связанной с задачей нахождения кратчайших путей для всех пар вершин.

В разделе 26.3 излагается алгоритм Джонсона. В отличие от других алгоритмов этой главы, он использует в своей работе списки смежных вершин, а не матрицу смежности. Время работы этого алгоритма есть 0(V2lgV + VE); таким образом, он эффективен для разреженных графов.

В последнем разделе (26.4) мы исследуем алгебраическую структуру (замкнутое полукольцо), позволяющую применить алгоритмы нахождения кратчайших путей для решения других задач с графами, в которых также требуется определить что-либо для всех пар вершин.

Всюду в этой главе мы рассматриваем граф G = (V, Е) с га , вершинами, так что \V\ = га. Мы будем обозначать матрицы большими буквами (например, W или D) а отдельные элементы матриц соответствующими маленькими буквами (wij,dij). Кроме того, мы будем использовать верхний индекс в скобках (напродобие jj(m) (d)), роль которого будет аналогична степени матрицы (см. ниже). Наконец, размер га квадратной га X га-матрицы А мы будем иногда записывать как rou?s[A] (rows - строки).

26.1 Кратчайшие пути и умножение матриц

В этом разделе мы рассмотрим алгоритм динамического программирования решения задачи нахождения кратчайших путей для всех пар вершин ориентированного графа G = (V,E). На каждом шаге он будет почти что умножать матрицы - только не вполне обычным образом. Сначала мы построим алгоритм со сложностью (временем работы) 0(С4), а затем улучшим его, получив оценку в (С3 lg V). Наше изложение будет следовать схеме алгоритма динамического программирования (глава 16)

Структура кратчайшего пути

Убедимся, что части решения являюётся решениями аналогичных подзадач. В нашем случае это означает, что отрезки кратчайшего пути сами являются кратчайшими путями между соответствующими вершинами (лемма 25.1).

Рекурсивная формула для длины кратчайшего пути

Пусть d обозначает минимальный вес пути из вершины i в