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

Решение:

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

Сначала найдём кратчайший путь из А в F:

• A → B → C → F: 8 + 3 + 3 = 14
• A → B → E → F: 8 + 3 + 1 = 12
• A → C → E → F: 3 + 4 + 1 = 8
• A → C → F: 3 + 3 = 6

Кратчайший путь из А в F равен 6 км (A → C → F).

Теперь найдём кратчайший путь из F в D:

• F → C → D: 3 + 3 = 6
• F → E → D: 1 + 3 = 4
• F → E → B → D: 1 + 3 + 3 = 7

Кратчайший путь из F в D равен 4 км (F → E → D).

Теперь сложим длины кратчайших путей A → F и F → D:

6 км (A → C → F) + 4 км (F → E → D) = 10 км.

Ответ: 10