Пример применения алгоритма Дейкстры

Необходимо найти все кратчайшие пути от вершины №1 для графа, представленого на рисунке

Составим матрицу длин кратчайших дуг для данного графа.

Cтартовая вершина, от которой строится дерево кратчайших путей – вершина 1.
Задаем стартовые условия: d(1)=0, d(x)=∞
Окрашиваем вершину 1, y=1.
Находим ближайшую вершину к окрашенной нами, используя формулу: d(x)=min{d(x); d(y)+ a_y,x}
d(2)=min{d(2)
; d(1)+a(1,2)}=min{∞; 0+10}=10
d(3)=min{d(3)
; d(1)+a(1,3)}=min{∞; 0+18}=18
d(4)=min{d(4)
; d(1)+a(1,4)}=min{∞; 0+8}=8
d(5)=min{d(5)
; d(1)+a(1,5)}=min{∞; 0+∞}=∞
d(6)=min{d(6)
; d(1)+a(1,6)}=min{∞; 0+∞}=∞
Минимальную длину имеет путь от вершины 1 до вершины 4 d(4)=8. Включаем вершину №4 в текущее ориентированноe дерево, а так же дугу ведущую в эту вершину. Согласно выражению это дуга (1,4)
d(2)=min{d(2)
; d(4)+a(4,2)}=min{10; 8+9}=10
d(3)=min{d(3)
; d(4)+a(4,3)}=min{18; 8+∞}=18
d(5)=min{d(5)
; d(4)+a(4,5)}=min{∞; 8+∞}=∞
d(6)=min{d(6)
; d(4)+a(4,6)}=min{∞; 8+12}=20
Минимальную длину имеет путь от вершины 1 до вершины 2 d(2)=10. Включаем вершину №2 в текущее ориентированноe дерево, а так же дугу ведущую в эту вершину. Согласно выражению это дуга (1,2)
d(3)=min{d(3)
; d(2)+a(2,3)}=min{18; 10+16}=18
d(5)=min{d(5)
; d(2)+a(2,5)}=min{∞; 10+21}=31
d(6)=min{d(6)
; d(2)+a(2,6)}=min{20; 10+∞}=20
Минимальную длину имеет путь от вершины 1 до вершины 3 d(3)=18. Включаем вершину №3 в текущее ориентированноe дерево, а так же дугу ведущую в эту вершину. Согласно выражению это дуга (1,3)
d(5)=min{d(5)
; d(3)+a(3,5)}=min{31; 18+15}=31
d(6)=min{d(6)
; d(3)+a(3,6)}=min{20; 18+∞}=20
Минимальную длину имеет путь от вершины 1 до вершины 6 d(6)=20. Включаем вершину №6 в текущее ориентированноe дерево, а так же дугу ведущую в эту вершину. Согласно выражению это дуга (4,6)
d(5)=min{d(5)
; d(6)+a(6,5)}=min{31; 20+23}=31
Минимальную длину имеет путь от вершины 1 до вершины 5 d(5)=31. Включаем вершину №5 в текущее ориентированноe дерево, а так же дугу ведущую в эту вершину. Согласно выражению это дуга (2,5)
Мы получили ориентированное дерево кратчайших путей начинающихся в вершине №1 для исходного графа .
d(1)=1 Длина маршрута L=0
d(2)=1-2 Длина маршрута L=10
d(3)=1-3 Длина маршрута L=18
d(4)=1-4 Длина маршрута L=8
d(5)=1-2-5 Длина маршрута L=31
d(6)=1-4-6 Длина маршрута L=20