с вершины 6, проходит по вершинам [6; 3; 5; 2; 4; 1]; или, начиная с вершины 1 – [1; 4; 2; 5; 3; 6].

7.4.4Алгоритм Дейкстры

Наиболее эффективный алгоритм решения задачи о кратчайшей s¡t цепи предложил Дейкстра. Рассматривается случай, когда все cij ¸ 0. Алгоритм Дейкстры заключается в такой разметке вершин, что на каждой итерации временная метка в данной вершине дает верхнюю границу длины цепи от s до этой вершины. Эти метки постепенно уменьшаются с помощью итерационной процедуры и на каждом шаге итерации одна из временных меток становится постоянной. Тогда метка уже не является верхней границей, а дает точную длину кратчайшей цепи от s к вершине с постоянной меткой. Метка вершины x имеет вид L(x) = [p; l(x)], где p – метка предшествования, l(x) – метка расстояния вершины x от s.

Описание алгоритма.

Шаг 0. Инициализация.

Назначить вершине s метку L(s) = [s; 0] и считать ее постоянной. Для всех x 6= y назначить метки

L(x) = [x; 1] и считать эти метки временными.

p := s.

Шаг 1. Обновление меток. Начало итерации.

Для всех x 2 ¡p (смежных с p), метки у которых временные, изменить метки следующим образом: если l(x) ¡ l(p) > c(p; x), то назначить метку [p; l(p) + c(p; x)], т.е.

l(x) = min[l(x); l(p) + c(p; x)].

Шаг 2. Превращение метки в постоянную.

Среди всех вершин с временными метками найти такую xy, для которой

l(xy) = min[l(x)]

x

Считать метку вершины xy постоянной. p := xy.

Шаг 3. Окончание разметки. Поиск цепи. Рассматриваются два варианта.

1. Требуется найти только цепь от s к t.

Если p = t, то l(t) – длина кратчайшей цепи от s к t; разметка закончена.

230 Глава 7. Связность графов

Если p =6 t, перейти на шаг 1.

2. Требуется найти кратчайшие цепи от s ко всем остальным вершинам.

Если все вершины помечены как постоянные, то эти метки дают длины кратчайших цепей; разметка закончена.

Если есть еще временные метки, перейти на шаг 1.

Шаг 4. Сама кратчайшая цепь строится точно так же, как и в алгоритме Форда. Начинаем с вершины t. Если ее метка есть L(t) = [x; l(t)], то x – вершина искомой цепи, предшествующая t, причем l(t) = l(x) + c(x; t). Далее, если метка вершины x есть L(x) = [y; l(x)], то y есть вершина, предшествующая x, причем l(x) = l(y) + c(y; x). Полагаем x = y и продолжаем итерации до тех пор, пока не станет x = s. Найденная таким образом цепь и есть искомая.

Теорема 7.4 Постоянная метка вершины x дает длину кратчайшей цепи из s в x.

Д о к а з а т е л ь с т в о . 1. Если все метки в графе постоянные, то доказательство то же, что и для алгоритма Форда.

2. Пусть S – множество вершин с постоянными метками, T – множество вершин с переменными метками.

Предположим, что на некоторой итерации разметки вершин постоянные метки дают длины кратчайших цепей (на первой итерации это очевидно). Нам нужно доказать, что кратчайшая цепь проходит только по вершинам из множества S.

Заметим, что на шаге 2 вершина xy с минимальной для временных меткой включается в S. Предположим теперь, что на некоторой следующей итерации кратчайшая цепь из s в xy не проходит полностью по вершинам из S и содержит по крайней мере одну вершину из T , и z 2 T – первая вершина в этой цепи, а вершина y 2 S – предшествует z в цепи. Тогда

c(s; z) = l(y) + c(y; z) ¸ l(z).

Так как l(z) – временная метка, а постоянная метка l(xy) выбрана на этой итерации как наименьшая из временных, то l(z) ¸ l(xy); поскольку cij ¸ 0, длина цепи между z и xy должна быть неотрицательной, что противоречит этому неравенству. Таким образом мы доказали: кратчайшая цепь из вершины s в xy проходит по вершинам с постоянными метками. По индукции доказательство продолжается до вершины t. £

Пример 7.8.

Рассмотрим граф из предыдущего примера: найти кратчайшую цепь из вершины 1 в вершину 6. Процесс разметки будем рассматривать на массивах меток

L(x) = [p(x); l(x)].

Получили p = xy = t. Сама цепь находится точно так же, как и в алгоритме Форда.

7.4.5Кратчайшие маршруты между всеми парами вершин. Алгоритм Флойда

Пусть задан взвешенный униграф (неориентированный, ориентированный, смешанный) G = (X; U) с матрицей весов C = kcijk =

kc(xi; xj)k, где cii = 0; i = 1; n; cij = 1, если нет ребра (xi; xj). Требуется найти кратчайшие маршруты между всеми парами вершин.

Введем следующую операцию композиции матрицы весов C - C = kc(2)ij k, где

c(2)ij = min[cij; cik + ckj]

при некотором фиксированном k. Алгоритм Флойда состоит в последовательном преобразовании матрицы весов. По завершении преобразований матрица весов представляет длины кратчайших цепей между всеми парами вершин. Для нахождения самих цепей определим матрицу цепей (или путей) P = kpijk. Под Ck и P k будем понимать соответствующие матрицы, полученные на k-ой итерации.

Описание алгоритма.

Шаг 1. Инициализация.

C0 := C; P 0 := (p0ij), где p0ij = i; k := 1;

Шаг 2. Для всех i; j = 1; : : : ; n выполнить операцию

Это значит:

s := ckik¡1 + ckkj¡1;

if ckij¡1 > s then begin

ckij := s; pkij := pkkj¡1;

end else

begin

ckij := ckij¡1; pkij := pkij¡1;

end

Шаг 3. Проверка на наличие циклов отрицательной длины.

Если ckll < 0; 1 · l · n, то алгоритм закончен: в графе имеется цикл отрицательной длины – решение невозможно.

Шаг 4. k := k + 1; Если k < n, то на Шаг 2.

Шаг 5. Получена матрица весов кратчайших цепей Cn и матрица самих цепей P n.

Кратчайшая цепь между вершинами xi; xj определяется следующим образом:

M(xi; xj) = [xi; : : : ; xj3 ; xj2 ; xj1 ; xj],

где j1 = Pijn; j2 = Pijn1 ; j3 = Pijn2 ; : : :, пока не получим Pijnm = i.

Теорема 7.5 Матрица Cn, полученная в результате работы алгоритма Флойда, является матрицей кратчайших расстояний между вершинами.

Д о к а з а т е л ь с т в о . Пусть кратчайшая цепь из вершины xi в вершину xj проходит последовательно через вершины x1; x2; : : : ; xq. Пусть k – первый шаг алгоритма, соответствующий какой-либо из этих вершин (пусть это будет вершина xl; пусть также xi = x0; xj = xq+1). До начала итераций непосредственный переход от xl¡1 к xl+1 не может быть короче, чем переход от xl¡1 к xl+1 через xl, так как в противном случае цепь

x0; : : : ; xl¡1; xl+1; : : : ; xq+1

была бы короче кратчайшей. После изменения длины перехода от xl¡1 до xl (на шаге k) цепь

x0; : : : ; xl¡1; xl+1; : : : ; xq+1

также становится кратчайшей. Повторяя этот процесс (переходя к новому k) установим, что в конце концов цепь из xi в xj становится кратчайшей. £

Пример 7.9.