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

Пусть 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;