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