Курсовая работа: Алгоритм Дейкстры

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

Шаг 2 . ;

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

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

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

Шаг 1 . .

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

Шаг 2 .

; ;

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

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

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

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

Шаг 2 .

; ;

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

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

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

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

Шаг 2 .

; ;

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

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

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

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

Шаг 2 .

;

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

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

К-во Просмотров: 747
Бесплатно скачать Курсовая работа: Алгоритм Дейкстры