Задание 2
Транспортному предприятию требуется перевезти груз из пункта 15+R (R – остаток от деления номера варианта на 12) в пункт А, где A=21+R, если R<6 и A=9+R, если R≥6. На рис. показана сеть дорог и стоимость перевозки единицы груза между отдельными пунктами. Определить маршрут доставки груза, которому соответствую наименьшие затраты.
№ варианта |
Значения | |||||||||||||||
6 |
а1 |
а2 |
а3 |
а4 |
а5 |
а6 |
а7 |
а8 |
а9 |
а10 |
а11 |
а12 |
а13 |
а14 |
а15 |
а16 |
19 |
17 |
24 |
15 |
13 |
36 |
15 |
38 |
18 |
45 |
18 |
17 |
17 |
15 |
18 |
17 | |
а17 |
а18 |
а19 |
а20 |
а21 |
а22 |
а23 |
а24 |
а25 |
а26 |
а27 |
а28 |
а29 |
а30 |
а31 |
а32 | |
52 |
39 |
16 |
18 |
43 |
35 |
11 |
17 |
21 |
44 |
17 |
15 |
12 |
22 |
58 |
42 | |
а33 |
а34 |
а35 |
а36 |
а37 |
а38 |
а39 |
а40 |
а41 |
а42 |
а43 |
а44 |
а45 |
а46 |
а47 |
а48 | |
33 |
90 |
45 |
70 |
70 |
90 |
11 |
15 |
18 |
22 |
90 |
33 |
12 |
60 |
44 |
33 |
Граф:
Сеть дорог между населенными пунктами
Решение:
Транспортному предприятию требуется перевезти груз из пункта 20 в пункт 26. Для нахождения кратчайшего пути между вершинами используется несколько алгоритмов, таких как алгоритм Дейкстры, алгоритм Форда и др. Но я использовал алгоритм Дейкстры:
Решая задачу алгоритмом Дейкстры, для удобства по ходу решения будем вести таблицу, в которую будем записывать данные (расстояния от одной вершины до другой):
После решения задачи по таблице определяем наименьший путь:
По значениям у вершины 26 поднимаемся от самого низу вверх, пока число не закончит повторяться. Потом перемещаемся по таблице как показано в таблице и делаем тоже самое, пока не поднимемся на самый верх.
Получим путь: 20→19→5→9→12→14→26.
Шаг №1. Определяем расстояния до каждой вершины и записываем значения в таблицу.
Шаг №2. Помечаем вершину с наименьшим расстоянием, и дальше, решая задачу, уже не будем обращать свое внимание на ней, будем определять расстояния до каждой вершины, не обращая внимание на помеченную вершину.
Шаг №3. Также помечаем вершину с наименьшим расстоянием и делаем все то же, что и на шаге №2. Также, сравнивая разные расстояния до одной вершины, выбираем наименьшее и записываем в таблицу.
Шаг №4.
Шаг №5.
Шаг №6.
Шаг №7.
Шаг №8.
Шаг №9.
Шаг №10.
Шаг №11.
Шаг №12.
Шаг №13.
Шаг №14.
Шаг №15.
Шаг №16.
Шаг №17.
Шаг №18.
Шаг №19.
Шаг №20.
В результате получим кратчайший путь от пункта 20 в пункт 26, который равен 113:
План перевозки груза при наименьших затратах от пункта 20 в пункт 26
В результате выполнения этой работы я научился работать с графом, находя наименьший путь с помощью метода Дейкстры, который может мне пригодиться и в будущем.