2. Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами А и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз. Таблица: A-B:10, A-C:20, A-D:20, B-A:10, B-C:10, C-A:20, C-B:10, C-D:9, C-E:1, D-A:20, D-C:9, D-E:7, E-C:1, E-D:7.

Решение:

Рассмотрим возможные пути из пункта А в пункт D, учитывая, что каждый пункт можно посетить только один раз:

1. А → D. Длина пути: 20 км.
2. А → B → C → D. Длина пути: 10 + 10 + 9 = 29 км.
3. А → C → D. Длина пути: 20 + 9 = 29 км.
4. А → C → E → D. Длина пути: 20 + 1 + 7 = 28 км.
5. А → B → C → E → D. Длина пути: 10 + 10 + 1 + 7 = 28 км.

Самый короткий путь — прямой путь из А в D.

Ответ: 20 км