Упр.3.50 ГДЗ Сборник упражнений Босова 7-9 класс (Информатика)

Между населенными пунктами А, Б, В, Г, Д построены дороги, протяженность которых в километрах приведена в таблице. Определите кратчайший путь между пунктами А и Г (при условии, что перемещаться можно только по построенным дорогам). Для решения задачи по таблице постройте схему, от схемы перейдите к дереву.

Из таблицы строим схему дорог и рассматриваем все возможные пути из пункта А в пункт Г.

Возможные маршруты:

• $$A \to Б \to В \to Г = 10 + 5 + 25 = 40$$
• $$A \to Б \to В \to Д \to Г = 10 + 5 + 5 + 15 = 35$$
• $$A \to В \to Г = 20 + 25 = 45$$
• $$A \to В \to Д \to Г = 20 + 5 + 15 = 40$$
• $$A \to Д \to Г = 30 + 15 = 45$$

Наименьшая длина пути получается по маршруту $$A \to Б \to В \to Д \to Г$$.

Ответ: $$АБВДГ = 35$$