Сети связи 3 задание. 3 задание сети связи. Алгоритм Дейкстры поиска кратчайшего пути

• Название: Алгоритм Дейкстры поиска кратчайшего пути
• Анкор: Сети связи 3 задание
• Дата: 14.11.2021
• Размер: 0.59 Mb.
• Имя файла: 3 задание сети связи.docx
• Тип: Документы; #271623

Домашняя работа по Сетям связи №3 Тема: «Алгоритм Дейкстры поиска кратчайшего пути»

Выполнил студент:

Вариант: №25

Москва 2021

№ Вар.	Вид графа	Веса рёбер графа
		S1	12	24	14	13	S3	3t	4t
5.	s ss So 3 s ssss s sss sss S 2 1 t 3 4	10	4	4	3	7	15	3	7

Первая итерация
₁ = min ₁ ; _s + c_s1 = min ∞, 0+10 = 10.

₂ = min ₂ ; _s + c_s2 = min ∞, 0+∞ = ∞.

₃ = min ₃ ; _s + c_s3 = min ∞, 0+15 = 15.

₄ = ∞.

_t = ∞.

₁

Минимальный вес имеет вершина 1, ей приписываем постоянный вес =3. = 10
Вторая итерация

Так как найдено новое значение i =1 t, то пересчитываем временные веса остальных вершин.

₂ = min ₁ ; ₁ + c₁₂ = min ∞, 10+4} = 14.

₃ = min ₂ ; ₁ + c₁₃ = min 15, 10+7 = 15.

4 = min₄ ; ₁ + c₁₄ = min∞, 10+3 = 13.

_t = ∞.

₄
Минимальный вес имеет вершина 4. Приписываем ей постоянный вес

= 13. Положим i =4.

Третья итерация

Так как найдено новое значение i=4  t, то пересчитываем временные веса вершин.

  min₂ ; ₄ + c₄₂ min1413+414;

₃  min ₄ ; ₄ + c₄₃ = min1513+∞15;

  min_t ; ₄ + c_4tmin∞13+7 = 20;


₂
Минимальный вес имеет вершина 2. Приписываем ей постоянный вес

= 14. Положим i =2.

Четвертая итерация

Так как найдено новое значение i =2t, то пересчитываем временные веса вершин.

₃ min₂ ; ₂ + c₂₃ min151415;

_t min_t ; ₄ + c_2t min2014 + 20;

₃
Минимальный вес имеет вершина 2. Приписываем ей постоянный вес

= 15. Положим i =3.

Пятая итерация.

Так как найдено новое значение i =2 t, то пересчитываем временные веса вершин.

_t = min _t ; ₃ + c_3t  = min  20, 15 + 3  = 18.

Минимальный вес имеет вершина t_t = 18. Положим i = t.

№ ите-рации	Веса узлов графа						Текущее дерево
	S	1	2	3	4	t
0. i = S	0	∞	∞	∞	∞	∞
1. i = 3	0		∞		∞	∞	1
2. i = 1	0					∞
3. i = 4	0					∞
4. i = 2	0					∞
5. i = t	0