Расчет тестового примера

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

Рис.35(Данный пример)

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

∞				∞	∞
	∞				∞
∞		∞	∞		∞
		∞	∞	∞
∞	∞	∞	∞	∞
∞	∞		∞		∞

Рис.36(Матрица длин кратчайших дуг)

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

Рис.37(Ориентированное дерево с корнем в вершине №1)

Дата добавления: 2015-08-31