Пр.10 «Нахождение кратчайших путей в графе. Алгоритм Дейкстры»

Отчет по практическим работам

ПО «МАТЕМАТИЧЕСКОМУ МОДЕЛИРОВАНИЮ»

 

 

ВЫПОЛНИЛА:

Студентка группы ИСП-О-18

Климова Е.С.

 

ПРОВЕРИЛА:

Шелепова Т.С.

 

Оценка ___________________

 

 

п. Электроизолятор

2020 г.

Пр.10 «Нахождение кратчайших путей в графе. Алгоритм Дейкстры»

    Цель:

    Приобретение навыков нахождения кратчайших путей в графе с помощью алгоритма Дейкстры.

Вариант 6.         

C12	C13	C14	C25	C27	C35	C36	C37	C45	C46	C47
8	1	5	9	2	6	8	4	5	2	6
C58	C59	C68	C69	C79	C8,10	C9,10
1	8	3	6	2	5	9

Решение:

Шаг 1

Включаем в S источник – вершину 1. Определим длины расстояний из источника до всех других вершин графа. Для всех вершин i, смежных с вершиной,1 положим длину пути из 1 в них, равной весу ребра их соединяющего . Для всех вершин, не смежных с вершиной 1 положим длину пути из 1 в них, равной ∞.

По условию задачи вершины смежные с 1 имеют номера 2, 3 и 4. Занесем данные в таблицу 1.

 

 

(Табл. 1)

S

D[2]

D[3]

D[4]

D[5]

D[6]

D[7]

D[8]

D[9]

D[10]

1

8

1

5

∞

∞

∞

∞

∞

∞

min(D[3]) = 1

Полученные данные изобразим на графе. Вершины, включенные в S на каждом шаге, будем помечать желтым цветом (рис. 1), пути до вершин, которые возможно определить на текущем шаге алгоритма – зеленым, путь минимальной длины на данном шаге – красным.

Рис. 1

Шаг 2

    По данным табл. 1, минимальным является путь из источника в вершину 3 равный D[3] = 1, следовательно, включаем в S вершину 3. также заносим в вектор предшественников для вершины 3 значение 1, так как на кратчайшем пути из вершины 1 в вершину 3 вершиной предшествующей вершине 3 является вершина 1, т.е. сам источник Prev[3] = 1.

Рис. 2

Имея в S вершины с номерами 1 и 3, определим минимальные длины путей, которые возможно построить из источника до других вершин графа, проходя только через 1 и 3. Здесь является минимальный путь из вершины 1 и направления к вершине 5. Занесем данные в табл. 2.

(Табл.2)

S	D[2]	D[3]	D[4]	D[5]	D[6]	D[7]	D[8]	D[9]	D[10]
1	8	1	5	∞	∞	∞	∞	∞	∞
1,3	8	1	5	min(1+6;∞) = 7	min(1+8;∞) = 9	min(1+4;∞) = 5	∞	∞	∞

 

min(D[4]) = 5

 

Шаг 3

По данным табл. 2 имеем минимальную вершину 4. Для вершины 4 предшествующий на минимальном пути к ней будет вершена 1, следовательно,  Prev[4] = 1.

 

Рис. 3

Имея в S вершины с номерами 1,3 и 4, пересчитаем длины путей, которые возможно построить из источника с помощью вершин множества S и выберем кратчайшее из них.

С включением вершины 4 в S кратчайшие пути в вершины 2 и 7 не появляются, однако через вершины 1 и 4 есть возможность определить минимальный на текущем шаге путь до вершины 5: D[6] = min(5 + 2) = 7. Данные занесем в табл. 3.

(Табл.3)

S	D[2]		D[3]		D[4]	D[5]		D[36]		D[8]
1	8		1		5	∞		∞		∞
1,3	8		1		5	min(1+6;10) = 7		min(1+8;∞) = 9		∞
1,3,4	8		1		5	7		9		∞
D[9]		D[10]		D[45]			D[46]		D[47]
∞		∞		∞			∞		∞
∞		∞		min(5+5;∞) = 10			min(5+2;∞) = 7		min(5+6;∞) =11
∞		∞		10			7		11

min(D[5]) = 7

 

Шаг 4

На этом шаге кратчайшим из источника является путь в вершину 5 равный D[5] = 7, включим в S вершину 5. Следовательно, Prev[5] = 3.

Рис. 4

При включении в S вершины 5 появляется путь из источника до вершины 8: D[8] = min(7+1) = 8. До других вершин кратчайшие пути не возникают. Занесем данные в табл. 4.

(Табл. 4)

S	D[2]	D[3]	D[4]	D[5]	D[6]
1	8	1	5	∞	∞
1,3	8	1	5	min(1+6;∞) = 7	min5+2;∞) = 7
1,3,4	8	1	5	7	7
1,3,4,37, 35, 36, 45, 46, 47	8	1	5	7	7
D[7]	D[8]	D[9]	D[10]	D[45]	D[46]
∞	∞	∞	∞	∞	∞
min(1+4;∞) = 5	∞	∞	∞	min(5+5;∞) = 10	min(5+2;∞) = 7
5	∞	∞	∞	10	7
5	min(7+1;∞) = 8	∞	∞	10	7

min(D[8]) = 8

 

Шаг 5.

Присоединяя вершину 8, мы получаем готовый граф.

И в итоге получается такая таблица:

S	D[2]	D[3]	D[4]	D[5]
1	8	1	5	∞
1,3	8	1	5	min(1+6;∞) = 7
1,3,4	8	1	5	7
1,3,4, 5, 6, 7, 8, 9	8	1	5	7
1,3,4, 5, 6, 7, 8, 9	8	1	5	7
1,3,4, 5, 6, 7, 8, 9, 10	8	1	5	7
D[6]	D[7]	D[8]	D[9]	D[10]
∞	∞	∞	∞	∞
min5+2;∞) = 7	min(1+4;∞) = 5	∞	∞	∞
7	5	∞	∞	∞
7	5	min(7+1;∞) = 8	∞	∞
7	5	8	13	min(8+5;8) = 13
7	5	8	13	13

min(D[10]) = 13

Таким образом, возможно сформулировать окончательные результаты работы алгоритма:

1. Кратчайшие пути от источника – вершины 1 до всех других вершин графа, а также значения вершин, предшествующих на этих путях, будут равны:

S	D[2]	D[3]	D[4]	D[5]	D[6]	D[7]	D[8]	D[9]	D[10]
min(D[i])=	8	1	5	7	7	5	9	13	13
Prev[i]=	1	1	3	4	4	4	4	5	6

 

2. Кратчайший путь от источника – вершины 1 до стока – вершины 10 будет равен:D[10] = 17 проходит через вершины:

I ->3->5->8->S.