Задание №4 — Теоретические основы информатики

#55872Задание №4ФИПИ

Графы

Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.

	A	B	C	D	E
A		4	2		8
B	4		7
C	2	7		2	6
D			2		3
E	8		6	3

Определите длину кратчайшего пути между пунктами B и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.

Правильный ответ

Пояснение

Решение. Для решения этой задачи мы построим дерево всех возможных путей из пункта B в пункт E, учитывая условие, что каждый пункт можно посетить только один раз. Это поможет нам наглядно сравнить длины маршрутов и найти кратчайший.

Выпишем все возможные маршруты, начиная из пункта B:

1. Путь через пункт A:
Из B можно поехать в A (длина $4$ ).
- Из A можно поехать в C (длина $2$ ). Из C можно поехать в D (длина $2$ ) или в E (длина $6$ ).
  а) Маршрут B — A — C — E: длина $4 + 2 + 6 = 12$ км.
  б) Маршрут B — A — C — D — E: длина $4 + 2 + 2 + 3 = 11$ км.
- Из A можно поехать сразу в E (длина $8$ ).
  в) Маршрут B — A — E: длина $4 + 8 = 12$ км.

2. Путь через пункт C:
Из B можно поехать в C (длина $7$ ).
- Из C можно поехать в A (длина $2$ ). Но из A мы можем поехать только в E (так как в B возвращаться нельзя).
  а) Маршрут B — C — A — E: длина $7 + 2 + 8 = 17$ км.
- Из C можно поехать в D (длина $2$ ).
  б) Маршрут B — C — D — E: длина $7 + 2 + 3 = 12$ км.
- Из C можно поехать сразу в E (длина $6$ ).
  в) Маршрут B — C — E: длина $7 + 6 = 13$ км.

Сравним полученные результаты:
- B — A — C — E: $12$ км
- B — A — C — D — E: $11$ км
- B — A — E: $12$ км
- B — C — A — E: $17$ км
- B — C — D — E: $12$ км
- B — C — E: $13$ км

Самым коротким оказался путь B — A — C — D — E, его длина составляет $11$ км.

Ответ: 11 км

Источник: ФИПИ