Упр.50 ГДЗ Рабочая тетрадь Босова 9 класс (Информатика)

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

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

• $$A \to Б \to Г = 10 + 15 = 25$$
• $$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$$

Наименьшая длина получается у пути А → Б → В → Д → Г.

Ответ

Кратчайший путь от А до Г: А – Б – В – Д – Г, его длина равна 35 км.