Задание 5. Изобразите дороги между пятью пунктами А, В, С, D, Е и их длины (в км): A-B=4, A-C=2, B-C=1, B-D=5, C-D=8, C-E=3, D-E=2. Найдите кратчайший путь из А в Е. Запишите маршрут (последовательность вершин) и его длину.

Решение:

Для нахождения кратчайшего пути из пункта А в пункт Е, мы можем использовать алгоритм Дейкстры или просто перебрать все возможные пути, учитывая заданные длины дорог.

Возможные пути из А в Е:

• А -> С -> Е: Длина = A-C + C-E = 2 + 3 = 5 км.
• А -> В -> С -> Е: Длина = A-B + B-C + C-E = 4 + 1 + 3 = 8 км.
• А -> С -> D -> Е: Длина = A-C + C-D + D-E = 2 + 8 + 2 = 12 км.
• А -> В -> D -> Е: Длина = A-B + B-D + D-E = 4 + 5 + 2 = 11 км.
• А -> В -> С -> D -> Е: Длина = A-B + B-C + C-D + D-E = 4 + 1 + 8 + 2 = 15 км.

Сравнивая длины всех возможных путей, мы видим, что кратчайший путь составляет 5 км.

Маршрут: А -> С -> Е

Длина: 5 км

Ответ: Маршрут А-С-Е, длина 5 км