Читать курсовая по математике: "Алгоритм Дейкстры" Страница 5

(Назад) (Cкачать работу)

;

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

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

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

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

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

; ;

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

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

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

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

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

;

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

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

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

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

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

;

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

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

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

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

Шаг 2. - только вершины x7, x6 и x9 имеют временные пометки.

; ;

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

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

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

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

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

;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Шаг 1. .

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

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

;

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

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

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

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

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

;

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

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

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

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

Шаг 2. ;

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

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

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

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

Шаг 2. ;

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

Шаг 4. x8

Похожие работы