Задача 3. Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами А и Е. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить не больше одного раза.

Кратчайший путь между пунктами А и Е можно определить, рассмотрев все возможные пути и выбрав самый короткий из них. Важно учесть, что каждый пункт можно посетить только один раз.

Возможные пути:

1. A → E: 9 км
2. A → B → E: 1 + 7 = 8 км
3. A → C → E: 15 + 3 = 18 км
4. A → B → C → E: 1 + 15 + 3 = 19 км
5. A → B → D → E: 1 + x + y (невозможно)
6. A → D → E: невозможно, т.к. нет прямого пути между A и D
7. A → B → C → D → E: 1 + 15 + 2 + 8 = 26 км
8. A → C → D → E: 15 + 2 + 8 = 25 км
9. A → B → C → E: 1 + 15 + 3 = 19 км

Сравним длины этих путей:

• A → E: 9 км
• A → B → E: 8 км
• A → C → E: 18 км
• A → B → C → E: 19 км
• A → B → C → D → E: 26 км
• A → C → D → E: 25 км

Самый короткий путь: A → B → E = 8 км

Ответ: 8