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

Из таблицы: A–B = 6, A–D = 19, B–D = 12, B–E = 5, C–D = 11, D–E = 3.

Проверим кратчайшие простые пути из A в E, проходящие через D:

• A–D–E: 19 + 3 = 22;
• A–B–D–E: 6 + 12 + 3 = 21;
• A–D–B–E: 19 + 12 + 5 = 36.

Пункт C соединён только с D, поэтому путь через C не может продолжиться к E без повторного посещения D.

Ответ: 21.