Курсовая работа: Алгоритм Дейкстры
Восьмая итерация
Шаг 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 .