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

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

Шаг 1.Положить и считать эту пометку постоянной.

Положить для всех и считать эти пометки временными. Положить p=s.

Шаг 2.Для всех , пометки которых временные, заменить пометки в соответствии со следующим выражением:

.

Шаг 3. Среди всех вершин со временными пометками найти такую, для которой: .

Шаг 4. Считать пометку вершины постоянной и положить .

Шаг 5.

Шаг 5. 1.Необходимо найтикратчайший маршрут только от к .

При алгоритм заканчивает работу, является длиной кратчайшего маршрута от s к . При p¹t перейти к шагу 2.

Шаг 5.2.Необходимо найтикратчайшие маршруты от s ко всем остальным вершинам графа.

Если все вершины получили постоянные пометки, то алгоритм заканчивает работу.

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

Как только длины кратчайших путей будут найдены, сами пути можно получить при помощи рекурсивной процедуры с использованием соотношения: l(i’)+c(i’,i)=l(i). Поскольку вершина i’непосредственно предшествует вершине iв кратчайшем пути от s к i, то для любой вершины iсоответствующую вершину i’можно найти как одну из оставшихся вершин, для которой выполняется: l(i’)+c(i’,i)=l(i).

Например: граф Gзадан графически и матрицей весов.

Найти кратчайшие расстояние в графе от первой вершины ко всем остальным.

Замечание:постоянные пометки будем выделять знаком +.

Матрица весов для графа C_G:

Шаг 1. l(1)=0

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

l(2)=l(3)=...=l(7)=∞

Устанавливаем временные пометки для вершин (2,...,7).

p=1

Шаг 2. – все вершины, смежные вершине 1 имеют временные пометки

l(3)=min(∞,0+4)=4 Изменяем временные

l(5)= min(∞,0+15)=15 пометки в соответствии с

l(6)= min(∞,0+13)=13выражением:

l(7)= min(∞,0+1)=1

Шаг 3.

, соответствует вершине .

Шаг 4.

l(7)=1⁺ –вершина 7 получает постоянную пометку

p=7

Шаг 5.Не все вершины имеют постоянные пометки, а только , алгоритм продолжает работу, переходим к шагу 2.

Шаг 2. среди них только вершина 1 имеет постоянную пометку.

l(2)=min(∞, 1⁺+7)=8

l(3)= min(4, 1⁺+2)=3

l(5)= min(15, 1⁺+11)=12

l(6)= min(13, 1⁺+12)=13

Шаг 3.

, соответствует вершине .

Шаг 4.

l(3)=3⁺ –вершина 3 получает постоянную пометку.

p=3

Шаг 5.Не все вершины имеют постоянные пометки, а только , алгоритм продолжает работу, переходим к шагу 2.

Шаг 2. . Постоянные пометки имеют вершины , их исключаем из рассмотрения.

l(4)= min(∞, 3⁺+9)=11

l(5)= min(12, 3⁺+12)=12

l(6)= min(13, 3⁺+13)=13

Шаг 3. Среди всех вершин с временными пометками, а это множество , находим:

, вершина 2 получает постоянную пометку.

Шаг 4.

l(2)=8⁺ –вершина 2 получает постоянную пометку.

p=2

Шаг 5.Не все вершины имеют постоянные пометки, а только , алгоритм продолжает работу, переходим к шагу 2.

Шаг 2. , вершина 7 имеет постоянную пометку, поэтому исключается из рассмотрения.

l(4)= min(12, 8⁺+4)=12

l(6)= min(13, 8⁺+5)=13

l(4)=l(5)=12⁺

p=4, 5

Можно выбирать как вершину 4, так и вершину 5. Выбираем вершину 4.

l(4)=12⁺

p=4

Множество вершин с постоянными пометками равно .

Шаг 2. , вершины 2 и 3 имеют постоянную пометку, следовательно, не рассматриваются.

l(5)= min(12, 12⁺+3)=12

, вершина 5 получает постоянную пометку.

l(5)=12⁺

p=5

Множество вершин с постоянными пометками равно .

Шаг 2. , все вершины, кроме 6имеют постоянные пометки.

l(6)= min(13,12⁺+2)=13

l(6)=13⁺

p=6

Множество вершин с постоянными пометками равно .

Шаг 5.Все вершины имеют постоянные пометки, алгоритм закончил работу. Найдены кратчайшие расстояния от вершины 1 ко всем остальным вершинам в графе.

Таким образом, кратчайшие маршруты от вершины 1:

1-7=(1,7)=1;

1-2=(1,7,2)=8;

1-3=(1,7,3)=3;

1-4=(1,7,3,4)=(1,7,2,4)=12;

1-5=(1,7,5)=12;

1-6=(1,6)=(1,7,6)=(1,7,2,6)=13;