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