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

Решение:

Граф дорог:

Поиск кратчайшего пути из А в Е:

Проанализируем возможные пути:

• A → C → E: 2 + 3 = 5 км
• A → B → C → E: 4 + 1 + 3 = 8 км
• A → B → D → E: 4 + 5 + 2 = 11 км
• A → C → D → E: 2 + 8 + 2 = 12 км

Кратчайшим является путь A → C → E.

Ответ: Маршрут A → C → E, длина 5 км.