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

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

Графы

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

	A	B	C	D	E
A		2	1		5
B	2		4
C	1	4		1	4
D			1		2
E	5		4	2

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

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

Пояснение

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

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

1) Путь B — A (длина $2$ ):
— Из A можно пойти в C: B — A — C (длина $2 + 1 = 3$ ).
— Из C можно пойти в D: B — A — C — D (длина $3 + 1 = 4$ ). Из D можно пойти в E: B — A — C — D — E. Длина: $4 + 2 = 6$ .
— Из C можно пойти в E: B — A — C — E. Длина: $3 + 4 = 7$ .
— Из A можно пойти в E напрямую: B — A — E. Длина: $2 + 5 = 7$ .

2) Путь B — C (длина $4$ ):
— Из C можно пойти в A: B — C — A (длина $4 + 1 = 5$ ). Из A можно пойти в E: B — C — A — E. Длина: $5 + 5 = 10$ .
— Из C можно пойти в D: B — C — D (длина $4 + 1 = 5$ ). Из D можно пойти в E: B — C — D — E. Длина: $5 + 2 = 7$ .
— Из C можно пойти в E напрямую: B — C — E. Длина: $4 + 4 = 8$ .

Теперь сравним длины всех найденных маршрутов:
1. B — A — C — D — E: $6$ км.
2. B — A — C — E: $7$ км.
3. B — A — E: $7$ км.
4. B — C — A — E: $10$ км.
5. B — C — D — E: $7$ км.
6. B — C — E: $8$ км.

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

Ответ: 6

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