Основы дискретной математики. Щипцов В.В - 12 стр.

UptoLike

ВУЗ: 

СЗТУ | Санкт-Петербург

Составители: 

Рубрика: 

12
Алгоритм, находящий этот кратчайший путь (алгоритм Дейкстры),
состоит в присваивании вершинам графа временных меток, которые по
определенному правилу заменяются постоянными. В общем виде
рассматриваемый алгоритм выглядит следующим образом.
Первой из двух выделенных вершин, скажем x
1
, присваиваем постоянную
метку O (расстояние вершины до самой себя), а всем остальным вершинам
присваиваем временные метки ∞ . Дальнейшая процедура состоит в том,
чтобы определенным образом
перемечать
вершины, присваивая некоторым из
них постоянные метки. Делается это так.
1. Если вершины x
j
не имеют окончательных меток и они являются
последователями вершины x
i
, которой на предыдущем шаге была присвоена
постоянная метка L
∗
(x
i
), то для каждой из вершин x
j
вычисляется новая
временная метка, равная
min L(x
j
), R
ij
+ L
∗
(x
i
), где (1)
L(x
j
) - старая временная метка вершины x
j
,
R
ij
- расстояние от вершины x
i
до x
j
.
2. Из всех
имеющихся временных меток (сюда входят не только метки
вершин x
j
, последователей вершины x
i
) выбирается наименьшая, которая
становится постоянной для своей вершины.
Процедура заканчивается после того, как второй из выделенных вершин,
до которой ищется кратчайший путь, будет присвоена постоянная метка. Затем
по имеющимся постоянным меткам восстанавливается кратчайший путь.
Рассмотрим конкретный пример.Пусть требуется найти кратчайший путь
между вершинами x
1
и x
8
в графе, приведенном на рис. 3. Расстояния между
вершинами графа даны в таблице 1 ( для простоты знак ∞ в таблице опущен).
Шаг 1. Полагаем L
∗
(x
1
)= 0 (знак ∗ у метки означает, что рассматриваемая
метка постоянная); L(x
j
) = ∞ ( j=2, 3, ... , 8) - все вершины, кроме первой,
имеют временные метки.
Шаг 2. Пусть Г(x
1
) - множество вершин - последователей вершины x
1
. В
нашем случае Г(x
1
) = x
2
, x
3
, x
4
, x
6
. Вычисляем новые временные метки
вершин из Г(x
1
) в соответствии с (1)
L( x
2
) = min ∞ , 2+0 = 2,
L( x
3
) = min ∞ , 1+0 = 1,
L( x
4
) = min ∞ , 6+0 = 6,
L( x
6
) = min ∞ , 9+0 =9.
Шаг 3. Превращаем временные метки в постоянные:
min L( x
j
) = min 2, 1, 6,∞, 9, ∞, ∞ = 1
2 ≤ j ≤ 8

Страницы