Шаг пятый

Шаг четвертый

Шаг третий

Шаг второй

Шаг первый

Поиск кратчайшего пути в графе

Поиск кратчайшего пути в графе между двумя точками - это нахождение такой последовательности дуг (или дуги), ведущей от начальной точки до конечной, при которой сумма их весов будет минимальной.

Рассмотрим задачу поиска кратчайшего пути между двумя заданными вершинами S и t для случая неотрицательной матрицы весов.

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

Рассмотрим суть алгоритма Дейкстры.

Пусть l(X_i) - пометка вершины X_i.

Присваивание начальных значений

Положить 1(S) = 0 и считать эту пометку постоянной.

Положить l(X_i) = ∞ для всех X_i ≠ S, и считать эти пометки временными.

Положить р = S,

где р- вспомогательная величина, равная номеру той вершины, которая на данном шаге получает постоянную пометку.

Обновление пометок

Для Х є Г(р), пометки которых временные, изменить их в соответствии со следующим выражением:

l(X_i)=min[ l(X_i); l(p)+c(p,X_i) ] (1)

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

Среди всех вершин с временными пометками найти такую, для которой l(X_i*)=min[l(X_i)]

Считать пометку вершины X_i* постоянной и положить p =X_i*.

а) Если надо найти путь от S к t:

- если p = t, то 1(р) является длиной кратчайшего пути, конец задачи;

- если р ≠ t, то перейти ко второму шагу.

б) Если требуется найти путь от S ко всем остальным вершинам:

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

- если некоторые пометки являются временными, перейти ко второму шагу.

Длина кратчайшего пути от исходной вершины S к любой вершине графа t равна величине постоянной пометки этой вершины t, т.е. l(S,t)=l(t ).

Для нахождения самого пути воспользуемся соотношением:

l(X_i*)+c(X_i*,X_i)=l(X_i), (2)

где X_i* - вершина, непосредственно предшествующая вершине X_i в кратчайшем пути от S к t

Если условие (2) выполняется, то дуга (X_i*,X_i) входит в кратчайший путь.

Используя изложенный выше алгоритм, определим кратчайший путь в графе G от заданной вершины Х₅ ко всем вершинам.

Шаг1 Присвоим начальные пометки вершинам:

l(X₅) = 0⁺;

X_i ≠ X₅, l(X_i) = ∞;

p = X₅,

Первая итерация

Шаг 2. Определим соответствие Г(р) и обновим временные пометки вершин, входящих в это соответствие.

Г(p) = Г(X₅) = {X₁, X₂, X₄, X₆}

обновляем пометки вершин X₁, X₂, X₄, X₆

l(X₁) = min{l(X₁); l(p) + c(p(X₁))} = min {∞, 0+5} = 5

l(X₂) = min{l(X₂); l(p) + c(p(X₂))} = min {∞, 0+7} = 7

l(X₄) = min{l(X₄); l(p) + c(p(X₄))} = min {∞, 0+10} = 10

l(X₆) = min{l(X₆); l(p) + c(p(X₆))} = min {∞, 0+8} = 8

Шаг 3. Выберем минимальную пометку из всех временных, сделаем ее постоянной и присвоим «р» номер, соответствующий этой вершине

min{5, 7, ∞, 10, 8} = 5 соответствует Х₁=> l(X₁*)= 5⁺

p= X₁

Так как не все вершины имеют постоянные пометки, то переходим к следующей итерации

Вторая итерация

Шаг 2. Определим соответствие Г(р) и обновим временные пометки вершин, входящих в это соответствие.

Г(p) = Г(X₅) = {X₂, X₃, X₅, X₆}

Так как вершина X₅ имеет постоянную пометку, то ее не рассматриваем.

l(X₂) = min{l(X₂); l(p) + c(p(X₂))} = min {7, 5+12} = 7

l(X₃) = min{l(X₃); l(p) + c(p(X₃))} = min {∞, 5+11} = 16

l(X₆) = min{l(X₆); l(p) + c(p(X₆))} = min {8, 5+10} = 8

min{7, 16, 10, 8} =7 соответствует X₂=> l(X₂*)= 7⁺

p= X₂

Так как не все вершины имеют постоянные пометки, то переходим к следующей итерации

Третья итерация

Шаг 2. Определим соответствие Г(р) и обновим временные пометки вершин, входящих в это соответствие.

Г(p) = Г(X₅) = {X₁, X₃, X₄, X₅}

Так как вершины X₁и X₅ имеет постоянные пометки, то их не рассматриваем.

l(X₃) = min{l(X₃); l(p) + c(p(X₃))} = min {16, 7+6} = 13

l(X₄) = min{l(X₄); l(p) + c(p(X₄))} = min {10, 7+3} = 10

min{13, 10, 8} = 8 соответствует X₆=> l(X₆*) = 4⁺

p= X₆

Так как не все вершины имеют постоянные пометки, то переходим к следующей итерации.

Четвёртая итерация

Шаг 2. Определим соответствие Г(р) и обновим временные пометки вершин, входящих в это соответствие.

Г(p) = Г(X₆) = {X₁, X₄, X₅}

Так как вершины X₁и X₅ имеет постоянные пометки, то их не рассматриваем.

l(X₄) = min{l(X₄); l(p) + c(p(X₄))} = min {10, 8+9} = 10

min{13, 10} = 10 => l(X₄*)= 5⁺

Так как вершина X₃единственная вершина с временной пометкой, то на этой итерации считаем l(X₃*)= 13

Так как все вершины имеют постоянные пометки, то итерационный процесс закончен. Пометки вершин дают точную длину кратчайшего пути от исходной вершины X₅ко всем вершинам.

Определим сами кратчайшие пути в графе. Для этого используется соотношение:

l(X_i*)+c(X_i*,X_i)= l(X_i),

Пусть Х_i = X₁, ей предшествуют вершины X₂; X₃; X₅; X₆

l(X₂) + c(X₂, X₁) = 7 + 12 = 19 ≠ l(X₁)

l(X₃) + c(X₃, X₁) = 13 + 11 = 24 ≠ l(X₁)

l(X₅) + c(X₅, X₁) = 0 + 5 = 5 = l(X₁)

l(X₆) + c(X₆, X₁) = 8 + 10 = 18 ≠ l(X₁)

Следовательно, дуга (X₅, X₁) входит в кратчайший путь

1) Пусть Х_i = X₂, ей предшествуют вершины X₁; X₃; X₄; X₅

l(X₁) + c(X₁, X₂) = 5 + 12 = 17 ≠ l(X₂)

l(X₃) + c(X₃, X₂) = 13 + 6 = 19 ≠ l(X₂)

l(X₄) + c(X₄, X₂) = 10 + 3 = 13 ≠ l(X₂)