Задача: Мистер Фокс собрался в путешествие. Для этого он узнал расстояния между пунктами A, B, C, D, E и занёс их в таблицу. Помогите мистеру Фоксу найти длину кратчайшего маршрута из пункта A в пункт E. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Таблица расстояний:
| A | B | C | D | E | |
| A | 2 | 3 | |||
| B | 2 | 5 | 1 | ||
| C | 3 | 5 | 2 | 2 | |
| D | 1 | 2 | 4 | ||
| E | 2 | 4 |
Решение:
Для решения этой задачи мы будем перебирать все возможные маршруты из пункта A в пункт E, посещая каждый пункт только один раз, и находить самый короткий из них.
Начнем из пункта A и будем записывать возможные пути и их длины:
1. Пути, начинающиеся с A → B:
- A → B (длина 2)
- Из B можно пойти в C или D.
- A → B → C (длина \(2 + 5 = 7\))
- Из C можно пойти в D или E.
- A → B → C → D (длина \(7 + 2 = 9\))
- Из D можно пойти в E.
- A → B → C → D → E (длина \(9 + 4 = 13\))
- A → B → C → E (длина \(7 + 2 = 9\))
- A → B → D (длина \(2 + 1 = 3\))
- Из D можно пойти в C или E.
- A → B → D → C (длина \(3 + 2 = 5\))
- Из C можно пойти в E.
- A → B → D → C → E (длина \(5 + 2 = 7\))
- A → B → D → E (длина \(3 + 4 = 7\))
2. Пути, начинающиеся с A → C:
- A → C (длина 3)
- Из C можно пойти в B, D или E.
- A → C → B (длина \(3 + 5 = 8\))
- Из B можно пойти в D.
- A → C → B → D (длина \(8 + 1 = 9\))
- Из D можно пойти в E.
- A → C → B → D → E (длина \(9 + 4 = 13\))
- A → C → D (длина \(3 + 2 = 5\))
- Из D можно пойти в B или E.
- A → C → D → B (длина \(5 + 1 = 6\))
- Из B можно пойти в E (но B не связан напрямую с E).
- A → C → D → E (длина \(5 + 4 = 9\))
- A → C → E (длина \(3 + 2 = 5\))
Теперь соберем все найденные маршруты из A в E и их длины:
- A → B → C → D → E: 13
- A → B → C → E: 9
- A → B → D → C → E: 7
- A → B → D → E: 7
- A → C → B → D → E: 13
- A → C → D → E: 9
- A → C → E: 5
Сравниваем все длины: 13, 9, 7, 7, 13, 9, 5.
Кратчайшая длина маршрута равна 5.
Кратчайший маршрут: A → C → E
Ответ:
Длина кратчайшего маршрута: 5
Пункты маршрута: ACE