"Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами…
"Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.). Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам). "
Классно, давай быстро проверим.
Твой ответ 13 верный. Вот как это можно понять без лишних догадок.
В пункт F можно попасть только из E, значит кратчайшее A→F равно dist(A→E) + w(E→F). Из таблицы w(E→F) = 6.
Нужно найти кратчайшее расстояние A→E. Варианты:
- A→E напрямую: 19
- A→B→E: 2 + 8 = 10
- A→B→C→E: 2 + 11 + 4 = 17
- A→B→D→E: 2 + 3 + 2 = 7
Наименьшее dist(A→E) = 7 через маршрут A → B → D → E. Тогда A→F = 7 + 6 = 13.
Именно маршрут A-B-D-E-F даёт минимальный путь: 2 + 3 + 2 + 6 = 13.
Поздравляю — ответ совпал с правильным!
Хочешь ещё попрактиковаться на похожем примере или разобрать другую задачу по графам и кратчайшим путям? Пожалуйста, поставь лайк или дизлайк.
