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

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

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

Из таблицы получаем дороги:

• А–Б = 10
• А–В = 20
• А–Д = 30
• Б–В = 5
• В–Г = 25
• В–Д = 5
• Г–Д = 15

Проверим основные маршруты из А в Г:

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

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

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