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

Решение:

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

1. А → С → Е

• Длина: \( A-C + C-E = 2 + 3 = 5 \) км.

2. А → В → С → Е

• Длина: \( A-B + B-C + C-E = 4 + 1 + 3 = 8 \) км.

3. А → В → D → Е

• Длина: \( A-B + B-D + D-E = 4 + 5 + 2 = 11 \) км.

4. А → С → D → Е

• Длина: \( A-C + C-D + D-E = 2 + 8 + 2 = 12 \) км.

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

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