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

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

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

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

Шаг 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 - исходная вершина графа.

Доверь свою работу ✍️ кандидату наук!
1500+ квалифицированных специалистов готовы вам помочь

Дата добавления: 2015-07-07; просмотров: 128 | Нарушение авторских прав


 

 

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

mybiblioteka.su - 2015-2022 год. (0.048 сек.)