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

Рассмотрим все возможные пары пунктов и кратчайшие расстояния между ними: 1) A и B: 9 2) A и C: 7 3) A и D: A -> B -> D = 9 + 4 = 13, A -> C -> D = 7 + 8 = 15. Кратчайший: 13. 4) B и C: B -> A -> C = 9 + 7 = 16, B -> D -> C = 4 + 8 = 12. Кратчайший: 12. 5) B и D: 4 6) C и D: 8 Наибольшее расстояние между пунктами A и D равно 15 (через C), но кратчайший путь 13 (через B). Наибольшее расстояние между пунктами B и C равно 16 (через A), но кратчайший путь 12 (через D). Наиболее удалены друг от друга пункты A и D. Кратчайший путь: A -> B -> D = 9 + 4 = 13. Ответ: 13