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

Question

Вопрос:

Accepted Answer

Путь A–D–C–E проходит через D, не повторяет пункты и имеет длину 6 + 2 + 2 = 10 км. Другой прямой путь через D, A–D–E, имеет длину 6 + 5 = 11 км.

Ответ: 10 км.