Задание 4. Между населёнными пунктами A, B, C, D, E, F построены дороги: AB = 3 км, AC = 9 км, BC = 4 км, BD = 7 км, CE = 2 км, DE = 3 км, DF = 4 км, EF = 6 км. Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.

Проверим основные маршруты из A в F:

• \(A\to B\to D\to F: 3+7+4=14\) км;
• \(A\to B\to C\to E\to F: 3+4+2+6=15\) км;
• \(A\to B\to C\to E\to D\to F: 3+4+2+3+4=16\) км;
• \(A\to C\to E\to D\to F: 9+2+3+4=18\) км.

Самый короткий маршрут — \(A\to B\to D\to F\).

Ответ: 14 км.