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

Рассмотрим алгоритм Дейкстры нахождения кратчайшей цепи между двумя заданными вершинами х_s и х_t.

Метод основан на приписывании вершинам временных пометок, причем пометка вершины x_i дает верхнюю границу длины пути от вершины х_s к этой вершине. Значения этих пометок постепенно уменьшаются на основе итерационной процедуры и на каждом шаге итерации точно одна из временных пометок становится постоянной. Это говорит о том, что пометка дает длину кратчайшей цепи от вершины х_s к рассматриваемой вершине.

Алгоритм:

Пусть l(x_i) ─ пометка x_i.

(блок присвоения начальных значений)

1. Пусть l(s) = 0. Положим l(x_i) =  для всех x_i  s и считаем их пометки временными; пусть p = s.

(блок обновления пометок)

2. Для всех x_i  Г(p), пометки которых временные, изменить пометки в соответствии с выражением

l(x_i)  min[l(x_i); l(p) + r(p, x_i)] (15.9)

(блок превращения пометки в постоянную)

3. Среди всех вершин с временными пометками найти такую, что l(x_i ^*) =

= min[l(x_i)].

4. Считать пометку x_i^* постоянной и положить p = x_i^*.

5.

а) Если надо построить цепь от вершины х_s к вершине х_t:

Если p = t, то l(p) ─ длина кратчайшей цепи, останов.

Если p  t, переход к п. 2.

б) Если надо построить цепь от вершины х_s ко всем остальным вершинам:

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

Если некоторые вершины являются временными, переход к п. 2.

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

Матрица смежности графа G имеет следующий вид:

	1	2	3	4	5	6	7
1	0	4	5	9	0	2	0	.
2	4	0	0	0	0	5	6
3	5	0	0	3	3	0	7
R = 4	9	0	3	0	8	0	0
5	0	0	3	8	0	0	1
6	2	5	0	0	0	0	3
7	0	6	7	0	1	3	0

Постоянные пометки будем обозначать *, остальные считаются временными.

Вначале нам необходимо выбрать начальную вершину x_s, которую мы будем использовать в дальнейшем, в качестве фиксированной. Примем в качестве такой вершины x₁. Метки всех остальных вершин, отличных от вершины x_1, считаем равными , а значение p = x₁.

1. L(x₁) = 0^*. L(x_i) = , x_i  x₁, p = x₁.

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

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

2. Для всех вершин, смежных с начальной вершиной x₁ и имеющих временные метки (x₁) = {x₂, x₃, x₄, x₆}, пересчитываем в соответствии с выражением (15.9) действующие значения их меток.

Для l(x₂)  min[  ; 0^*+ 4 ] = 4.

Для l(x₃)  min[  ; 0^*+ 5 ] = 5.

Для l(x₄)  min[  ; 0^*+ 9 ] = 9.

Для l(x₆)  min[  ; 0^*+ 2 ] = 2.

3. Выбираем из списка вершин с временными метками вершину с временной меткой, имеющей минимальное значение:

Min [ 4, 5 , 9, , 2,  ]

x₂ x₃ x₄ x₅ x₆ x₇

Очевидно, что такой вершиной является вершина x₆.

4. Вершина x₆ получает постоянную пометку l(x₆) = 2^*, значение p = x₆.

5. Поскольку не все вершины имеют постоянные пометки, переходим к п. 2.

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

2. Для всех вершин, смежных с текущей вершиной x₆ и имеющих временные метки (x₆) = {x₂, x₇}, пересчитываем в соответствии с выражением (15.9) действующие значения их меток:

Для l(x₂)  min[ 4 ; 2^*+ 5 ] = 4.

Для l(x₇)  min[  ; 2^*+ 3 ] = 5.

Новое значение метки для вершины x₂ оказалось больше текущего, поэтому оставляем текущее значение временной метки, а для вершины x₇ заменяем значение l(x₇) =  на полученное значение l(x₇) = 5.

3. Выбираем из списка вершин с временными метками вершину с временной меткой, имеющей минимальное значение:

Min[ 4, 5, 9, , 5]

x₂ x₃ x₄ x₅ x₇

Очевидно, что такой вершиной является вершина x₂.

4. Вершина x₂ получает постоянную пометку l(x₂) = 4^*, значение p = x₂.

5. Поскольку не все вершины имеют постоянные пометки, переходим к п. 2.

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

2. Для всех вершин, смежных с текущей вершиной x₂ и имеющих временные метки (x₂) = {x₇}, пересчитываем в соответствии с выражением (15.9) действующие значения их меток.

Для l(x₇)  min[ 5 ; 4^*+ 6 ] = 5.

Новое значение метки для вершины x₇ оказалось больше текущего, поэтому оставляем текущее значение временной метки l(x₇) = 5.

3. Выбираем из списка вершин с временными метками вершину с временной меткой, имеющей минимальное значение:

Min [ 5 , 9, , 5 ]

x₃ x₄ x₅ x₇

В данном случае две вершины имеют одинаковые метки l(x₃) = l(x₇) = 5 и мы можем выбрать любую из них. Пусть это будет вершина x₃.

4. Вершина x₃ получает постоянную пометку l(x₃) = 5^*, значение p = x₃.

5. Поскольку не все вершины имеют постоянные пометки, переходим к п. 2.

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

2. Для всех вершин, смежных с текущей вершиной x₃ и имеющих временные метки (x₃) = {x₄, x₅, x₇} пересчитываем в соответствии с выражением (1.9) действующие значения их меток:

для l(x₄)  min[ 9 ; 5^*+ 3 ] = 8,

для l(x₅)  min[  ; 5^*+ 3 ] = 8,

для l(x₇)  min[ 5 ; 5^*+ 7 ] = 5.

Новое значение метки для вершины x₇ оказалось больше текущего, поэтому оставляем текущее значение временной метки, а для вершин x₄ и x₅ заменяем текущие значения меток на новые.

3. Выбираем из списка вершин с временными метками, вершину с временной меткой, имеющей минимальное значение:

Min [ 8, 8, 5 ]

x₄ x₅ x₇

Очевидно, что такой вершиной является вершина x₇.

4. Вершина x₇ получает постоянную пометку l(x₇) = 5^*, значение p = x₇.

5. Не все вершины имеют постоянные пометки, переходим к п. 2.

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

2. Для всех вершин, смежных с текущей вершиной x₇ и имеющих временные метки (x₇) = {x₅}, пересчитываем в соответствии с выражением (15.9) действующие значения их меток.

Для l(x₅)  min[ 8 ; 5^*+ 1 ] = 6.

3. Выбираем из списка вершин с временными метками вершину с временной меткой, имеющей минимальное значение:

Min [ 8, 6 ]

x₄ x₅

Такой вершиной является вершина x₅.

4. Вершина x₅ получает постоянную пометку l(x₅) = 6^*, значение p = x₅.

5. Поскольку не все вершины имеют постоянные пометки, переходим к п. 2.

Шестая итерация

2. Из вершин, смежных с текущей вершиной x₃ и имеющих временные метки осталась только вершина x₄: (x₁) = {x₄}. Пересчитываем значение ее метки в соответствии с выражением (15.9):

для l(x₄)  min[ 8 ; 6^*+ 8 ] = 8.

Новое значение метки для вершины x₄ оказалось больше текущего, поэтому оставляем текущее значение временной метки.

3. В списке вершин с временными метками только один элемент:

Min [ 8, ]

x₄

4. Вершина x₄ получает постоянную пометку l(x₄) = 8^*, значение p = x₄.

5. Поскольку все вершины графа имеют постоянные метки, конец алгоритма.

Таким образом, мы построили кратчайшие пути от вершины x₁ до вершин x₂, x₃, x₆ напрямую:

x₁  x₂(4^*), x₁  x₃(5^*), x₁  x₆(2^*),

а до вершин x₄, x₅, x₇ через промежуточные:

x₁  x₃  x₄(8^*);

x₁  x₆  x₇  x₅(6^*);

x₁  x₆  x₇(5^*).

Длину цепи x_s  x_i, т.е. суммарную стоимость весов пройденных ребер, можно получить при помощи рекурсивной процедуры:

l(x_s) + r(x_s, x_j) = l(x_i),

т.е. проверяется, какая из вершин, смежных вершине x_s, дает вместе с весом ребра r(x_s, x_j) сумму, равную l(x_i).

Например: l(x₄) = 8. Поскольку вершина x₄ напрямую не связана с вершиной x₁, то определим кратчайший путь из x₁ в x₄:

l(x₁) = l(x₄) ─ r(x₃, x₄) = 8 – 3 = 5 = l(x₃) - r(x₁, x₃) = 5 – 5 = 0.

Таким образом, построена кратчайшая цепь между вершинами x₁ и x₄: x₁  x₃  x₄.