|
Читайте также: |
Нулевая итерация
Шаг 1.
Обозначим через l(xi) пометку вершины xi (длина пути от x1 до xi).
Положить s = x1 и l(x1) = 0+ и считать эту величину постоянной пметкой.
Положить l(xi) = ∞ для всех xi ≠ x1 и считать эти пометки временными.
Положить p = x1
Таким образом, все вершины графа помечены: (x1 – постоянной пометкой; xi – переменной пометкой, где i = 2,3,…,9) и выполнена нулевая итерация.
Обновление пометок
Первая итерация
Шаг 2.
Найдем соответствие вершины графа, имеющей постоянную метку, т.е. Г(x1), а это– множествовершин, являющихся конечными вершинами дуг, у которых начальной вершиной является x1:
Г(x1) = {x2, x7, x8, x9}. У этого множества вершин все пометки временные, равные ∞. Найдем постоянную пометку, для чего сначала находим пометки для каждой из этих вершин x2, x7, x8, x9 по зависимости: 
, тогда:
l(x2) = min[l(x2), l(x1)+c(x1,x2)] = min[∞, 0 + 10] = 10;
l(x7) = min[l(x7), l(x1)+c(x1,x7)] = min[∞, 0 + 3] = 3;
l(x8) = min[l(x8), l(x1)+c(x1,x8)] = min[∞, 0 + 6] = 6;
l(x9) = min[l(x9), l(x1)+c(x1,x9)] = min[∞, 0 + 12] = 12.
Перевод пометок из временных в постоянные.
Шаг 3.
Среди всех вершин с временными пометками найти такую, для которой выполняется условие: 
, т.е.
min[l(x2), l(x7), l(x8), l(x9), l(x3), l(x4), l(x5), l(x6)] = min[10, 3, 6, 12, ∞, ∞, ∞, ∞] =
= 3 = l(x7)
Шаг 4. Вершина графа x7 получает постоянную метку
3+ = l(x7), а
p = x7
Шаг 5. Постоянной пометкой помечены только две вершины: x1 и x7, но если не все вершины отмечены как постоянные, то требуется все повторить начиная со второго шага. Пометки в начале второй итерации показаны на рис. а)
а) 10 ∞
3+
∞
0+
 |
12 ∞
6 ∞
Вторая итерация
Шаг 2.
Найдем соответствие вершины графа, имеющей новую постоянную метку, т.е. Г(x7), а это– множествовершин, являющихся конечными вершинами дуг, у которых начальной вершиной является x7:
Г(x7) = {x2, x4, x6, x9}. У этого множества вершин все пометки временные, равные ∞. Найдем постоянную пометку, для чего сначала находим пометки для каждой из этих вершин x2, x4, x6, x9 по зависимости: , тогда:
l(x2) = min[l(x2), l(x7)+c(x7,x2)] = min[∞, 3 + 2] = 5;
l(x4) = min[l(x4), l(x7)+c(x7,x4)] = min[∞, 3 + 4] = 7;
l(x6) = min[l(x6), l(x7)+c(x7,x6)] = min[∞, 3 + 14] = 17;
l(x9) = min[l(x9), l(x7)+c(x7,x9)] = min[∞, 3 + 24] = 27.
Перевод пометок из временных в постоянные.
Шаг 3.
Среди всех вершин с временными пометками найти такую, для которой выполняется условие: , т.е.
min[l(x2), l(x4), l(x6), l(x9), l(x3), l(x5), l(x8)] = min[5, 7, 17, 27, ∞, ∞, ∞,] =
= 5 = l(x2)
Шаг 4. Вершина графа x2 получает постоянную пометку
5+ = l(x2), а
p = x2
Шаг 5. Постоянной пометкой помечены только три вершины: x1,x2 и x7, но если не все вершины отмечены как постоянные, то требуется все повторить начиная со второго шага. Пометки в начале третий итерации показаны на рис. б)
б) 5+ ∞
3+
7
0+
|
12 ∞
6 ∞
Третья итерация
Шаг 2.
Найдем соответствие вершины графа, имеющей новую постоянную метку, т.е. Г(x2), а это– множествовершин, являющихся конечными вершинами дуг, у которых начальной вершиной является x2:
Г(x2) = {x1, x3, x7, x9}. Из этого множества только вершины x3, и x9 имеют пометки временные, равные ∞.
l(x3) = min[l(x3), l(x2)+c(x2,x3)] = min[∞, 5 + 18] = 23;
l(x9) = min[l(x9), l(x2)+c(x2,x9)] = min[∞, 5 + 13] = 18.
Перевод пометок из временных в постоянные.
Шаг 3.
min[l(x2), l(x4), l(x6), l(x8), l(x9), l(x5)] = min[23, 7, 17, 6,18, ∞,] =
= 6 = l(x8)
Шаг 4. Вершина графа x2 получает постоянную пометку
6+ = l(x8), а
p = x8
Шаг 5. Постоянной пометкой помечены только три вершины: x1,x2,x7 и x8 но если не все вершины отмечены как постоянные, то требуется все повторить начиная со второго шага. Пометки в начале четвертой итерации показаны на рис. в)
в)
б) 5+ ∞
3+
7
0+
|
12 ∞
6 ∞
Четвертая итерация
Таким образом, все вершины графа помечены постоянными пометками.
Окончательная пометка вершин и x1 -база
5+ 23+
3+
7+
0+
|
11+ 17+
6+ 12+
Алгоритм Дейкстры для вычисления дерева кратчайших путей
(псевдоязык Паскаля)
Вход: огргаф G(V,E) Заданный матрицей длин дуг C:array [1…p, 1…p] of real и списками смежности Г; s - исходная вершина графа.
Дата добавления: 2015-07-07; просмотров: 128 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Неотрицательная матрица весов | | | Понятие и характеристика современного мирового хозяйства. |