Вариант 2. Между населенными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.

Из таблицы следуют дороги: A—B — 8 км, A—E — 5 км, B—D — 3 км, B—E — 3 км, C—D — 2 км, C—E — 1 км.

Проверяем возможные простые пути из A в D: A—B—D = 8 + 3 = 11 км; A—E—B—D = 5 + 3 + 3 = 11 км; A—E—C—D = 5 + 1 + 2 = 8 км.

Кратчайший из них — путь A—E—C—D.

Ответ: 8 км.