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

Алгоритм Дейкстры находит кратчайший путь между двумя данными вершинами в (ор)графе, если длины дуг неотрицательны.

Алгоритм 8.4. алгоритм Дейкстры

Вход: орграф G(V,E), заданный матрицей длин дуг С : array [l..p,l..p] of real; s и t -

вершины графа. Выход: векторы Т : array [l..p] of real; и Я : array [l..p] of O..p. Если вершина v лежит на

кратчайшем пути от s к t, то T[v] — длина кратчайшего пути от s к v; H(v] — вершина, непосредственно предшествующая v на кратчайшем пути. for v from I to p do

T[v]: = oo { кратчайший путь неизвестен }

X[v] : = 0 { все вершины не отмечены } end for

H[s]: = 0 { s ничего не предшествует } T[s]: = 0 { кратчайший путь имеет длину 0 ... }

X[s] : = !{... и он известен } v : = s { текущая вершина } М: { обновление пометок } for и € P⁽v) do

if X[u\ = 0 & Т{и] > T[v] + C[v, и] then

Т[и] : = T[v] + C[v,u] { найден более короткий путь из s в и через v } Н[и] :=v{ запоминаем его }

end if end for t: = oo;u: = 0

{ поиск конца кратчайшего пути } for и from I to p do

if X[u] = 0&2>] < £ then

v : = и; t: = Т [и] { вершина v заканчивает кратчайший путь из S}

end if end for if v = 0 then

stop { нет пути из s в t} end if if v = t then

stop { найден кратчайший путь из s в t} end if

X[v]: = 1 { найден кратчайший путь из s в v} goto M

ЗАМЕЧАНИЕ -

Для применимости алгоритма Дейкстры достаточно выполнения более слабого условия, [ положительность длин дуг. А именно, достаточно выполнения неравенства треуголъ-

. Vu, v, w е V d(u, v) ^ d(u, w) + d(w, v), которое, очевидно, выполняется, если длины дуг неотрицательны.

обоснование

Для доказательства корректности алгоритма Дейкстры достаточно заметить, что каждом выполнении тела цикла, начинающегося меткой М в качестве v мьзуетея вершина, для которой известен кратчайший путь из вершины s •ими словами, если X[v] = 1, то 7>] = d(s,v), и все вершины на пути (,,») ределяемом вектором Я, обладают тем же свойством, то есть

\/u T[u] = 1 =*. T[u] = d(s,u)bT[H[u]] = 1.

Действительно (по индукции), первый раз в качестве v используется вершина s я которой кратчайший путь пустой и имеет длину 0 (непустые пути не мо-ггь короче, потому что длины дуг неотрицательны) Пусть ТЫ = d(s u] * всех ранее помеченных вершин и. Рассмотрим вновь помеченную верши­ну v, которая выбрана из условия T[v] = min 2>]. Заметим, что если известен

Л ['ttj ^^0 путь, проходящий через помеченные вершины, то тем самым известен кратчай­ ший путь. Допустим (от противного), что T[v] > d(s,v), то есть найденный путь, ведущий из s в v, не является кратчайшим. Тогда на этом пути должны быть непомеченные вершины. Рассмотрим первую вершину w на этом пути, такую что T[w] = 0. Имеем: T[w] = d(s,w) ^ d(s,v) < T[v], что противоречит выбору вершиныv.

коментарии

Изложение центрального результата этой главы — теоремы Менгера 8.3.2 и со­путствующего материала — в основном следует в [23].

Алгоритм нахождения максимального потока в сети заимствован из [11] с небольшими модификациям Алгоритм выделения компонент сильной связности приведен в [5], где имеется весьма полный обзор различных алгоритмов обхода и анализа графов, применя­емых в программировании. Алгоритмы Флойда и Дейкстры нахождения крат­чайших путей принадлежит к числу классических общеизвестных алгоритмов, описание которых можно найти в большинстве учебников по дискретной мате­матике, в частности, в [14, 11].

Упражнения

Доказать, что если 5(G) > (р - 1)/2, то граф G связен.

Доказать вторую теорему подраздела 8.2.1.

Как может измениться количество компонент сильной связности орграфа при добавлении к нему одной дуги?

Пусть в графе G(V,E) заданы вероятности успешного прохождения дуг, О ^ P[v] ^ 1. Вероятность успешного прохождения пути определяется как произведение вероятностей составляющих его дуг. Построить алгоритм на­ хождения наиболее надежного (то есть имеющего наибольшую вероятность) пути от вершины s к вершине t.