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

Решение:
1. Найдем все возможные пути из А в D, считая длину каждого пути:
- A - C - D : 20 + 9 = 29
- A - E - D : 20 + 7 = 27
- A - B - C - D : 10 + 10 + 9 = 29
- A - C - E - D : 20 + 1 + 7 = 28
2. Выбираем самый короткий путь. Путь A - E - D является самым коротким.
Ответ: 27