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

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

Шаг 2 .

;

Шаг 3 . соответствует x₈ .

Шаг 4 . x₈ получает постоянную пометку l(x₈ )=16⁺ , p=x₈ .

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

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

Шаг 2 .

;

Шаг 3 . соответствует x₇ .

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

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

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

Шаг 2 .

; ;

Шаг 3 . соответствует x₁₀ .

Шаг 4 . x₁₀ получает постоянную пометку l(x₁₀ )=18⁺ , p=x₁₀ .

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

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

Шаг 2 . ;

Шаг 3 . соответствует x₅ .

Шаг 4 . x₅ получает постоянную пометку l(x₅ )=19⁺ , p=x₅ .

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

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

Шаг 2 . ;

Шаг 3 . x₉ получает постоянную пометку l(x₉ )=21⁺ .

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

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

Шаг 1 . .