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

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

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

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

Шаг 2 . - только вершины x₅ , x₆ и x₉ имеют временные пометки.

; ;

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

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

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

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

Шаг 2 . - только вершины x₅ , x₆ и x₃ имеют временные пометки.

; ;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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