Алгоритм Дейкстры (стр. 3 из 4)
Третья итерация
Шаг 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 ко всем другим вершинам графа.
дискретный математика программа интерфейс
| 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.
соответствует 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 получает постоянную пометку l(x8)=14+, p=x8.
Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.
Пятая итерация
Шаг 2.
; 
Шаг 3.
соответствует x3.Шаг 4. x3 получает постоянную пометку l(x3)=14+, p=x3.
Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.
Шестая итерация
Шаг 2.
; 
Шаг 3.
соответствует x9.Шаг 4. x9 получает постоянную пометку l(x9)=19+, p=x9.
Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.
Седьмая итерация
Шаг 2.
; 
Шаг 3.
соответствует x5.Шаг 4. x5 получает постоянную пометку l(x5)=17+, p=x5.
Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.
Восьмая итерация
Шаг 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.