Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
Определите длину кратчайшего пути между пунктами A и E. Каждый пункт можно посетить только один раз.
Решение:
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
|
A |
B |
C |
D |
E |
| A |
* |
2 |
6 |
4 |
|
| B |
2 |
* |
3 |
|
|
| C |
6 |
3 |
* |
3 |
2 |
| D |
4 |
|
3 |
* |
|
| E |
|
|
2 |
|
* |
Необходимо определить длину кратчайшего пути между пунктами A и E, при условии, что каждый пункт можно посетить только один раз.
Рассмотрим возможные пути:
- A -> B -> C -> E: A -> B = 2 км, B -> C = 3 км, C -> E = 2 км, суммарное расстояние = 7 км.
- A -> C -> E: A -> C = 6 км, C -> E = 2 км, суммарное расстояние = 8 км.
- A -> D -> C -> E: A -> D = 4 км, D -> C = 3 км, C -> E = 2 км, суммарное расстояние = 9 км.
Наименьшее расстояние среди возможных маршрутов — 7 километров, оно соответствует маршруту A -> B -> C -> E.
Ответ: длина кратчайшего пути между пунктами A и E составляет 7 километров.
Ответ: 7