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