Алгоритм Дейкстры (стр. 2 из 4)
Как только длины кратчайших путей от s будут найдены (они будут заключительными значениями пометок вершин), сами пути можно получить при помощи рекурсивной процедуры с использованием соотношения (*). Так как вершина xi' непосредственно предшествует вершине xi в кратчайшем пути от s к xi, то для любой вершины xi соответствующую вершину xi' можно найти как одну из оставшихся вершин, для которой
' 
' 
. (*)Если кратчайший путь от s до любой вершины xi является единственным, то дуги (xi', xi) этого кратчайшего пути образуют ориентированное дерево с корнем s. Если существует несколько «кратчайших» путей от s к какой-либо другой вершине, то при некоторой фиксированной вершине xi' соотношение (*) будет выполняться для более чем одной вершины xi. В этом случае выбор может быть либо произвольным (если нужен какой-то один кратчайший путь между s и xi), либо таким, что рассматриваются все дуги (xi', xi), входящие в какой-либо из кратчайших путей и при этом совокупность всех таких дуг образует не ориентированное дерево, а общий граф, называемый базой относительноs или кратко – s-базой.
2.2 Задачи с методическим описанием
Найти кратчайшие пути от вершины 1 ко всем другим вершинам графа
Неориентированное ребро будем рассматривать как пару противоположно ориентированных дуг равного веса. Воспользуемся алгоритмом Дейкстры. Постоянные пометки будем снабжать знаком +, остальные пометки рассматриваются как временные.
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 |
| x1 | 10 | 3 | 6 | 12 | ||||
| x2 | 10 | 18 | 2 | 13 | ||||
| x3 | 18 | 25 | 20 | 7 | ||||
| x4 | 25 | 5 | 16 | 4 | ||||
| x5 | 5 | 10 | ||||||
| x6 | 20 | 10 | 14 | 15 | 9 | |||
| x7 | 2 | 4 | 14 | 24 | ||||
| x8 | 6 | 23 | 15 | 5 | ||||
| x9 | 12 | 13 | 9 | 24 | 5 |
Алгоритм работает так:
Шаг 1.
.Первая итерация
Шаг 2.
- все пометки временные. 
; 
; 
; 
Шаг 3.
соответствует x7.Шаг 4. x7 получает постоянную пометку l(x7)=3+, p=x7.
Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.
Вторая итерация
Шаг 2.
- все пометки временные. 
; 
; 
; 
Шаг 3.
соответствует x2.Шаг 4. x2 получает постоянную пометку l(x2)=5+, p=x2.
Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.
Третья итерация
Шаг 2.
- только вершины x3 и x9 имеют временные пометки. 
; 
Шаг 3.
соответствует x8.Шаг 4. x8 получает постоянную пометку l(x8)=6+, p=x8.
Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.
Четвертая итерация
Шаг 2.
- только вершины x5, x6 и x9 имеют временные пометки. 
; 
; 
Шаг 3.
соответствует x4.Шаг 4. x4 получает постоянную пометку l(x4)=7+, p=x4.
Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.
Пятая итерация
Шаг 2.
- только вершины x5, x6 и x3 имеют временные пометки. 
; 
; 
Шаг 3.
соответствует x9.Шаг 4. x9 получает постоянную пометку l(x9)=11+, p=x9.
Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.
Шестая итерация
Шаг 2.
- только вершина x6 имеет временную пометку. 
Шаг 3.
соответствует x5.Шаг 4. x5 получает постоянную пометку l(x5)=12+, p=x5.
Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.
Седьмая итерация
Шаг 2.
- только вершина x6 имеет временную пометку. 
Шаг 3.
соответствует x6.Шаг 4. x6 получает постоянную пометку l(x5)=17+, p=x6.
Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.
Восьмая итерация
Шаг 2.
- только вершина x3 имеет временную пометку. 
Шаг 3. x3 получает постоянную пометку l(x3)=23+.
Найти кратчайшие пути от вершины 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.