Курсовая работа: Алгоритм Дейкстры
Найти кратчайшие пути от вершины 1 ко всем другим вершинам графа
Неориентированное ребро будем рассматривать как пару противоположно ориентированных дуг равного веса. Воспользуемся алгоритмом Дейкстры. Постоянные пометки будем снабжать знаком +, остальные пометки рассматриваются как временные.
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 |
| x1 | 3 | 2 | ||||||
| x2 | 5 | 15 | 12 | |||||
| x3 | 8 | 24 | ||||||
| x4 | 6 | 8 | 18 | 4 | 11 | |||
| x5 | 12 | 7 | 20 | |||||
| x6 | 20 | 9 | 13 | |||||
| x7 | 10 | 4 | 9 | 16 | ||||
| x8 | 24 | 16 | 22 | |||||
| x9 | 11 | 13 |
Алгоритм работает так:
Шаг 1 . 
.
Первая итерация
Шаг 2 . 
- все пометки временные.
; 
Шаг 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.
Пятая итерация