2. Между населёнными пунктами A, B, C, D, E построены дороги. Длины дорог (км): AB = 8, AE = 5, BD = 3, BE = 3, CD = 2, CE = 1. Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.

Сравним варианты последнего участка пути до D. Через B дорога BD имеет длину 3 км. К B можно приехать из A напрямую (8 км) или через E (5 + 3 км), поэтому путь через B составляет не менее 11 км.

Через C дорога CD составляет 2 км. К C кратчайший путь из A проходит через E: AE + EC = 5 + 1 = 6 км. Получаем общий путь 6 + 2 = 8 км.

Путь A–E–C–D не посещает ни один пункт повторно.

Ответ: 8 км; маршрут A–E–C–D.