вершину j, если рассматривать пути с не более чем т рёбрами. При т = 0 допустимы лишь «пути» вовсе без рёбер, то есть

d(o) j 0 если i = j,

оо если г ф j.

Если же т 1, то минимум d достигается либо на пути из не

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

4т) = тт(4т 1) mm {d{~l) + wkj}) =

r j(m-l) .-i

(Последнее равенство использует равенство Wjj = 0.)

Если граф не содержит циклов с отрицательными весами, кратчайший путь можно выбрать без циклов; такой путь содержит не более га - 1 рёбер. Следовательно,

s(ij) = 4?-v = 4? = 4?+v = .., (2б.з)

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

По заданной матрице весов W = (wij) мы будем последовательно

вычислять матрицыD2\ ... , D1, где Dm) = (m)). Как

мы видели, последняя матрицабудет содержать веса крат-

чайших путей. Заметим, что матрица(веса путей из одного

ребра) совпадает с W.

Шаг алгоритма состоит в вычислении Dm) По JJ)(m 1) и W.

{\sc Extend-Shortest-Paths}$(D,W)$\\

\verb \verb \verb \verb \verb \verb \verb \verb

1$n \leftarrow rows[D]$\\

2пусть $D=(d {ij>)$ --- $n\times п$-матрица

3I for $i \leftarrow 1$ to $n$\\

4I do for $j \leftarrow 1$ to $n$\\

5I do $d {ij> \leftarrow \infty$\\

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

7I do $d {ij> \leftarrow \min(d {

8I return $D$\\

Эта процедура вычисляет матрицу D в соответствии с формулой (26.2) при этом роль матриц D и D играют матрицы JJ)(m 1) и 7J)(m). Процедура содержит три вложенных цикла, так что время её работы есть в (га3).

Чтобы увидеть аналогию этой процедуры с процессом умножения матриц, запишем процедуру умножения матриц А ж В размером га X га по формуле

п

ctJ = агк bkj(26.4)

k=i

{\sc Matrix-Multiply}$(A,B)$\\ \verbl $n \leftarrow rows[A]$\\

\verb2 Iпусть $C=(c {ij})$---$n\times п$-матрица

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

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

\verb5I do $c {ij> \leftarrow 0$\\

\verb6I for $k \leftarrow 1$ to $n$\\

\verb7I do $c {ij} \leftarrow c {ij}+a {ik}\cdot

b {kj>$\\

\verb8 I return $C$

Видно, что эта процедура получается из предыдущей заменами

d(m-l)

а,

w -7> Ь, rf(m) -> с, min -т- +,

+•

При этом символу оо, являющемуся нейтральным элементом для операции min (в том смысле, что min(oo,a) = а, соответствует число 0, являющееся нейтральным элементов для операции + (0 + а = а).

С точки зрения этой аналогии, мы как бы вычисляем «произведение» га-1 экземпляров матрицы W с помощью последовательных умножений:

Результат этих «умножений», матрица= Wn~l содержит

веса кратчайших путей. Оформим описанное вычисление в виде процедуры (с временем работы О (га4)):

{\sc Slow-All-Paths-Shortest-Paths}$(W)$\\ \verb11 I$n \leftarrow rows[W]$\\

( о

DC1)

-4\

оо оо 2

3 7 2

V8

О

4 оо

оо оо /О 3

оо О

-5 оо -3 -4 О

оо 1 7 оо оо О 6 2 1 5

1 -5 О 1 6

/ о

оо

О )

-1 11 -2

О /

£>(2)

£>(4)

3

оо 2 8

/О

3 7 2

\8

О

4

-1 оо 1 О

4

-1 5

О

1

-5 О 1 6

-4\

7 11 -2

О / -4\

-1 3

-2 О /

Рис. 26.1 26.1 Ориентированный граф G и последовательность матриц DmK Можно убедиться, что матрица

£>(5) = d(4) . w

значит, и все последующие)

будет равна £>4.

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

\verb3I for $m \leftarrow 2$ to $n-l$\\

\verb4I do $D~{(m)} \leftarrow \mbox{\sc Extend-Shortest-Paths}(D~{(m-:

)$\\

\verb5I return $D~{(n-l)}$\\

На рис. 26.1 показан пример графа и соответствующих ему матриц L>(m).

Более быстрый способ

Заметим, что мы вычисляем все матрицы Dm\ хотя нас интересует лишь матрица

D(n-i)

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

Аналогичным образом мы мы можем определить Dn выполнив всего \lg(n - 1)] умножений матриц, вычисляя матрицы в последовательности

L>W=W

L)(2)=W2=W-W,

£)(4)=W4=W2-W2,

£)(8)=W8=W-W4,

то тех пор, пока показатель степени станет большим или равным п-1 (при этом он будет равен 2Г1§(П 1)1, как легко видеть).

Реализуем этот метод повторного возведения в квадрат (repeated squaring) в виде процедуры:

{\sc Faster-All-Pairs-Shortest-Paths}$(W)$\\