1. Между населёнными пунктами A, B, C, D, E построены дороги. Длины дорог: A–B — 6, A–C — 1, A–E — 1, B–D — 1, C–D — 2, C–E — 2, D–E — 1. Определите длину кратчайшего пути между пунктами A и B, проходящего через пункт E. Каждый пункт можно посетить только один раз.

Ищем маршрут из A в B, который проходит через E и не посещает пункты повторно.

1. Маршрут A–E–D–B проходит через E, а все его дороги есть в таблице.
2. Его длина: 1 + 1 + 1 = 3.
3. Чтобы попасть из E в B, кратчайший вариант — E–D–B длиной 1 + 1 = 2; путь A–E имеет длину 1. Значит, короче 3 быть не может.

Ответ: 3.