ЕГЭ и ОГЭ
Главная

Источник задания: Решение 2438. ЕГЭ 2017. Информатика. В.Р. Лещинер. 10 вариантов.

Задание 3. Между населёнными пунктами А, В, С, D, Е, F, Z построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

Определите длину кратчайшего пути между пунктами А и Z (при условии, что передвигаться можно только по построенным дорогам).

Решение.

Нарисуем граф связи точек А, В, С, D, Е, F, Z, в котором вес дуг будет соответствовать расстоянию между двумя соответствующими пунктами (см. рисунок ниже).

Из рисунка графа видно, что кратчайший маршрут точки A до точки Z проходит по точкам ACDEZ и равен 7+2+4+7=20.

Ответ: 20.

Другие задания:

Темы раздела

Для наших пользователей досутпны следующие материалы: