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

; ;

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

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

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

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

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

;

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

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

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

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

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

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

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

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

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

Шаг 2 . временных пометок нет.

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

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

дискретный математика программа интерфейс

x1	x2	x3	x4	x5	x6	x7	x8	x9
x1
x2	9
x3	8	3
x4	7
x5	6
x6	17	4
x7	4
x8	7
x9	9	5

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

Шаг 1 . .

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

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

;

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

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

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