Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Решение. Нулевая итерация

Читайте также:
  1. Графическое решение.
  2. Ответственное решение.
  3. Параллактический треугольник и его решение.
  4. По результатам рассмотрения жалобы выносится решение.
  5. Разрешение.
  6. Решение.
  7. Решение.

Нулевая итерация

Шаг 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 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Неотрицательная матрица весов| Понятие и характеристика современного мирового хозяйства.

mybiblioteka.su - 2015-2021 год. (0.013 сек.)