Задание 3. Между населёнными пунктами А, В, С, D, Е, F, Z построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
Определите длину кратчайшего пути между пунктами А и Z (при условии, что передвигаться можно только по построенным дорогам).
Решение.
Ниже на рисунке представлен граф расстояний между точками пунктов. Дуги этого графа пронумерованы в соответствии с расстояниями между соответствующими пунктами.
Из графа видно, что минимальное расстояние от A до Z соответствует маршруту ACDZ с расстоянием 7+6+14=27.
Ответ: 27.
Другие задания:
Для наших пользователей доступны следующие материалы: