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

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

По таблице строим схему дорог:

• $$A \leftrightarrow Б = 10$$
• $$A \leftrightarrow В = 20$$
• $$A \leftrightarrow Д = 30$$
• $$Б \leftrightarrow В = 5$$
• $$В \leftrightarrow Г = 25$$
• $$В \leftrightarrow Д = 5$$
• $$Г \leftrightarrow Д = 15$$

Проверим возможные пути из $$A$$ в $$Г$$:

• $$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$$