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

Решение:

Нам нужно найти кратчайший путь из пункта А в пункт D, который обязательно проходит через пункт В. Мы можем пройти А → В → D.

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

• А → В: длина 1.
• А → C → B: длина 5 + 6 = 11.
• А → E → B: длина 2 + 7 = 9.

Кратчайший путь из А в В равен 1 (путь А → В).

Теперь рассмотрим пути из В в D:

• В → D: длина 6.
• В → C → D: длина 1 + 1 = 2.
• В → E → D: длина 7 + 2 = 9.

Кратчайший путь из В в D равен 2 (путь В → C → D).

Теперь соединим кратчайшие пути: А → В → C → D.

Длина этого пути: 1 (А→В) + 2 (В→C→D) = 3.

Проверим, проходим ли мы через пункт В и посещаем ли пункты только один раз. Путь: А, В, С, D. Все условия соблюдены.

Ответ: 3