№4. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз. Данные таблицы: A–B 2, A–C 3, A–D 7, A–F 15; B–D 3; C–D 1; D–E 2, D–F 11; E–F 3.

Рассмотрим маршруты от A к F по указанным дорогам. Через D и E получаем маршрут A–C–D–E–F длиной 3 + 1 + 2 + 3 = 9 км. Другие возможные короткие пути: A–B–D–E–F — 2 + 3 + 2 + 3 = 10 км; A–D–E–F — 7 + 2 + 3 = 12 км; прямая дорога A–F — 15 км.

Маршрут A–C–D–E–F не повторяет пункты, поэтому он допустим и короче остальных.

Ответ: 9 км