Между населёнными пунктами 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. Каждый пункт можно посетить только один раз.
Ответ:
Реальный Вариант ОГЭ 2024 по информатике @twocod – задание №4
Решение:
Между населёнными пунктами 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