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

Решение:

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

Граф дорог:

Расчет кратчайшего пути:

Уточнение для D:

• A -> D: 9 (через B)
• A -> C -> D: 2 + 8 = 10
• A -> B -> C -> D: 4 + 1 + 8 = 13
• A -> C -> B -> D: 2 + 1 + 5 = 8
• Кратчайший путь до D: A-C-B-D, длина 8

Уточнение для E:

• A -> C -> E: 2 + 3 = 5
• A -> C -> D -> E: 2 + 8 + 2 = 12
• A -> B -> D -> E: 4 + 5 + 2 = 11
• A -> C -> B -> D -> E: 2 + 1 + 5 + 2 = 10
• Кратчайший путь до E: A-C-E, длина 5

Ответ: Кратчайший путь из А в Е: A-C-E, длина 5 км.