Question

На схеме изображены дороги между населенными пунктами A, B, C, D и указаны протяженности этих дорог. Определите, какие два пункта наиболее удалены друг от друга. Укажите длину кратчайшего пути между ними.
Нужно полное решение:)

Answer 1

Ответ: длина кратчайшего пути между A и D равна 13

Смотря на картинку видно, что единственными населенными пунктами между которыми нет прямой дороги (дороги, которая не проходит через другие населенные пункты) являются A и D. Следовательно они и являются населенными пунктами наиболее удалёнными друг от друга.

Рассмотрим варианты пути межу ними:

1) A->B->D = 9 + 4 = 13

2) A->C->D = 7 + 8 = 15

3) С заездом в пункт C дорога станет ещё длиннее