Рис. 26.2 26.2 Взвешенный ориентированный граф, используемый в упр. 26.11, 26.2-1 и 26.3-1.

\verb1 $п \leftarrow rows[W]$\\ \verb2 $D~{(1)} \leftarrow W$\\ \verb3 $m \leftarrow 1$\\ \verb4 I while $n-l > m$\\

\verb5I do $D~{(2m)> \leftarrow \mbox{\sc Extend-Shortest-Paths}(D~{

D4(m)})$\\

\verb6$m \leftarrow 2m$\\

\verb7 I return $D~{(m)}$

На каждом шаге цикла while в строках 4-6 вычисляется JJ)(2m) = и значение т удваивается, пока т не станет большим или равным п - 1.

Время работы такой процедуры составляет 0(ra3lgra), т.к. всего выполняется [lg(ra - 1)] «умножений» матриц, каждое из которых требует 0(га3) действий. Алгоритм довольно прост, и можно надеяться, что константа, скрытая в О-обозначени, будет небольшой.

[Заметим, что мы неявно использовали ассоциативность нашего «умножения» матриц, переходя к другому способу вычисления степеней. Её можно проверить по аналогии с доказательством ассоциативности для обычного умножения - либо заменить ссылку на ассоциативность прямым доказательством того, что JJ)(2m) есть произведение Jj(m) на Dm\ которое легко провести, рассматривая две половины пути длины 2т.]

Упражнения

26.1-1 Проследите за исполнением алгоритмов Slow-All-Pairs-Shortest-Paths и Faster-All-Pairs-Shortest-Paths на графе рис. 26.2. Вычислите все возникающие при этом матрицы.

26.1-2 Где используется, что шц = 0 при всех г?

26.1-3 Что соответствует матрице

если продолжить аналогию с обычным умножением матриц?

26.1-4 Представьте задачу поиска кратчайших путей из одной вершины как задачу отыскания произведений и вектора. Как в этих терминах выглядит алгоритм Беллмана-Форда (см. раздел 25.3)?

26.1-5 Придумайте алгоритм вычисления матрицы предшествования П по уже имеющейся матрице D весов кратчайших путей за

время О (га3).

26.1-6 С другой стороны, матрицы предшествования могут вычисляться параллельно с вычислением весов. Будем брать в качествепредшествующую j вершину на каком-нибудь кратчайшем пути из i в j, состоящем не более чем из то ребер. Измените процедуры Extend-Shortest-Paths и Slow-All-Pairs-Shortest-Paths так, чтобы они в дополнение к

вычисляли ещё и матрицы П1), П2), ... , П-1).

26.1-7 Процедура Faster-All-Pairs-Shortest-Paths (в её нынешнем виде) использует [~lg(ra - 1)] матриц (массивов) размером га X га. Общий объем памяти, таким образом, составляет ©(га2 lgra). Измените её так, чтобы использовать всего два массива размером га X га (тем самым уменьшив объём памяти до ©(га2)).

26.7-8 Измените алгоритм Faster-All-Pairs-Shortest-Paths так, чтобы он обнаруживал наличие в графе цикла с отрицательным весом.

26.1-9 Придумайте эффективный алгоритм определения минимального числа рёбер в цикле отрицательного веса (для данного графа; предполагается, что такой цикл существует).

26.1. Алгоритм Флойда-Уоршолла

В этом разделе мы рассмотрим другой способ решения задачи о кратчайших путях для всех пар вершин ориентированного взвешенного графа, также основанный на технике динамического программирования. Этот способ (алгоритм Флойда-Уоршолла) работает за время О (С3). Мы по-прежнему допускаем рёбра с отрицательным весом, но запрещаем циклы отрицательного веса.

Кроме того, мы рассмотрим алгоритм нахождения транзитивного замыкания графа, основанный на той же идее.

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

Алгоритмы предыдущего раздела выделяли последнее ребро пути. Алгоритм Флойда-Уоршалла действует иначе: для него важно, какие вершины используются в качестве промежуточных, и особую роль играют промежуточные вершины с максимальным номером (в некоторой нумерации вершин). Промежуточной (intermediate) вершиной простого пути р = (v\, v2, vi) будем называть любую ИЗ ВерШИН v2,v3, ... , v{-\.

Будем считать, что вершинами графа G являются числа 1,2,...,п. Рассмотрим произвольное к га. Для данной пары вершин i,j G V рассмотрим все пути из г в j, у которых все промежуточные вершины принадлежат множеству {1,2,...,к}. Пусть р - путь минимального веса среди всех таких путей. Он будет простым, так как в графе нет циклов с отрицательным

весом. Как найти вес этого пути, зная веса всех таких путей (для всех пар вершин) для меньших к? Для пути р есть две возможности.

Если к не входит в р, все промежуточные вершины пути р содержатся в множестве {1, 2,... , к - 1}. Тогда путь р является кратчайшим путём из i в j, промежуточные вершины которого принадлежат множеству {1, 2,... , к - 1}.

Если к является промежуточной вершиной пути р, она разбивает его на два участка р\ и р2 (вершина к встречается лишь однажды, так как р - простой путь), см. рис. 26.3. По лемме 25.1 путь р\ будет кратчайшим путём из г в к с промежуточными вершинами из множества {1,2,... , к - 1}. Путь р2 является кратчайшим путём из к в j с промежуточными вершинами из множества {1, 2,... , к - 1}.

Рекурентная формула для длин кратчайших путей

Эти рассуждения позволяют написать другую (по сравнению с приведённой в разделе 26.1) рекурентную формулу для длин крат-

(к)

чайших путей. Обозначим через cQ- вес кратчайшего пути из вершины г в вершину j с промежуточными вершинами из множества {1, 2,... , к}. При к = 0 промежуточных вершин нет вовсе, поэтому

df = Wij. В общем случае

Ак) \ ™чесли к = О,

d- = { min(4-1), dtl) + dg 1)) -ли * £ 1.

Матрица = (cQ™ ) содержит искомое решение. Другими словами, dff = 5(i,j) для всех i,j £ V, поскольку разрешены любые промежуточные вершины.

Вычисление кратчайших путей снизу вверх

Напишем процедуру, которая вычисляет веса кратчайших путей, последовательно находя значения d для к = 1, 2,... , п. Её входм является матрица W размером га X га (веса рёбер графа), результатом является матрица весов кратчайших путей.

{\sc Floyd-Warshall>$(W)$\\

\verb11 I$n \leftarrow rows[W]$\\

\verb2 $D~{(0)> \leftarrow W$\\

\verb3 I for $k \leftarrow 1$ to $n$\\

\verb4I do for $i \leftarrow 1$ to $n$\\

\verb5I do for $j \leftarrow 1$ to $n$\\

\verb6l$d~{(k)} {ij> \leftarrow \min(d~{(k-l)} {ij},

d-{(k-l)} {ik}+d-{(k-l)} {kj})$\\

\verb7 I return $D~{(n)}$

На рисунке 26.4 показан ориентированный раф и матрицы Dk\ вычисляемые этим алгоритмом.