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

Путь B–C–A–D–E–F проходит по дорогам длиной 1, 1, 2, 2 и 3 км. Его общая длина: 1 + 1 + 2 + 2 + 3 = 9 км. К пункту F ведёт только дорога E–F, поэтому путь должен пройти через E; более короткого пути от B до E, чем B–C–A–D–E, нет.

Ответ: 9 км.