Читать курсовая по математике: "Алгоритм Дейкстры" Страница 4

(Назад) (Cкачать работу)

4

14

24

x8

6

23

15

5

x9

12

13

9

24

5

Алгоритм работает так:

Шаг 1. .

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

Шаг 2. - все пометки временные.

; ; ;

Шаг 3.соответствует x7.

Шаг 4. x7 получает постоянную пометку l(x7)=3+, p=x7.

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.

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

Шаг 2. - все пометки временные.

; ; ;

Шаг 3.соответствует x2.

Шаг 4. x2 получает постоянную пометку l(x2)=5+, p=x2.

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.

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

Шаг 2. - только вершины x3 и x9 имеют временные пометки.

;

Шаг 3.соответствует x8.

Шаг 4. x8 получает постоянную пометку l(x8)=6+, p=x8.

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.

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

Шаг 2. - только вершины x5, x6 и x9 имеют временные пометки.

; ;

Шаг 3.соответствует x4.

Шаг 4. x4 получает постоянную пометку l(x4)=7+, p=x4.

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.

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

Шаг 2. - только вершины x5, x6 и x3 имеют временные пометки.

; ;

Шаг 3.соответствует x9.

Шаг 4. x9 получает постоянную пометку l(x9)=11+, p=x9.

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.

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

Шаг 2. - только вершина x6 имеет временную пометку.

Шаг 3.соответствует x5.

Шаг 4. x5 получает постоянную пометку l(x5)=12+, p=x5.

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.

Седьмая итерация

Шаг 2. - только вершина x6 имеет временную пометку.

Шаг 3.соответствует x6.

Шаг 4. x6 получает постоянную пометку l(x5)=17+, p=x6.

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.

Восьмая итерация

Шаг 2. - только вершина x3 имеет временную пометку.

Шаг 3. x3 получает постоянную пометку l(x3)=23+.

Найти кратчайшие пути от вершины 1 ко всем другим вершинам графа

Неориентированное ребро будем рассматривать как пару противоположно ориентированных дуг равного веса. Воспользуемся алгоритмом Дейкстры. Постоянные пометки будем снабжать знаком +, остальные пометки рассматриваются как временные.

Алгоритм работает так:

Шаг 1. .

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

Шаг 2. - все пометки

Похожие работы