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

Решение:

1. Визуализация графа:

Нарисуем граф, где пункты — это вершины, а дороги — рёбра с указанием их длины.

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

Будем перебирать возможные пути из А в Е и их длины:

• Путь 1: A → C → E
• Длина: A-C (2) + C-E (3) = 5 км
• Путь 2: A → B → D → E
• Длина: A-B (4) + B-D (5) + D-E (2) = 11 км
• Путь 3: A → C → D → E
• Длина: A-C (2) + C-D (8) + D-E (2) = 12 км
• Путь 4: A → B → C → E
• Длина: A-B (4) + B-C (1) + C-E (3) = 8 км
• Путь 5: A → B → C → D → E
• Длина: A-B (4) + B-C (1) + C-D (8) + D-E (2) = 15 км

Сравнивая длины всех найденных путей, видим, что кратчайший путь — это A → C → E, его длина 5 км.

Ответ:

• Кратчайший путь из А в Е: A → C → E
• Его длина: 5 км