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

На схеме нарисованы дороги между населёнными пунктами А, В, C, D, E и указаны их протяжённости. Определите, какие два населённых пункта наиболее удалены друг от друга (при условии, что передвигаться можно только по указанным на схеме дорогам). В ответе укажите кратчайшее расстояние между этими населёнными пунктами.

Найдём кратчайшие расстояния между парами пунктов, между которыми нет прямой дороги, и выберем наибольшее из них.

Из схемы получаем дороги:

• $$A B = 40$$, $$A C = 40$$, $$C B = 60$$;
• $$A E = 80$$, $$E D = 50$$, $$D B = 10$$.

Рассмотрим пары пунктов без прямого сообщения:

• $$A D$$: $$A \to B \to D = 40 + 10 = 50$$, $$A \to E \to D = 80 + 50 = 130$$. Кратчайшее: $$50$$.
• $$C D$$: $$C \to B \to D = 60 + 10 = 70$$, $$C \to A \to E \to D = 40 + 80 + 50 = 170$$, $$C \to A \to B \to D = 40 + 40 + 10 = 90$$. Кратчайшее: $$70$$.
• $$B E$$: $$B \to D \to E = 10 + 50 = 60$$, $$B \to A \to E = 40 + 80 = 120$$. Кратчайшее: $$60$$.
• $$C E$$: $$C \to A \to E = 40 + 80 = 120$$, $$C \to B \to D \to E = 60 + 10 + 50 = 120$$, $$C \to B \to A \to E = 60 + 40 + 80 = 180$$. Кратчайшее: $$120$$.

Наибольшее из кратчайших расстояний равно $$120$$.

Ответ

1