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

#55510Задание №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 и Е. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.

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

Пояснение

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

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

1) Путь A — B — C — E
Из A в B дорога равна $2$ км.
Из B в C дорога равна $3$ км.
Из C в E дорога равна $2$ км.
Длина пути: $2 + 3 + 2 = 7$ км.

2) Путь A — B — C — D — E
Из A в B дорога равна $2$ км.
Из B в C дорога равна $3$ км.
Из C в D дорога равна $3$ км.
Из D в E дорога равна $0$ (дороги нет, согласно таблице).
Внимание: В таблице на пересечении D и E стоит пустое место, значит, прямой дороги между ними нет. Этот путь невозможен.

3) Путь A — C — E
Из A в C дорога равна $6$ км.
Из C в E дорога равна $2$ км.
Длина пути: $6 + 2 = 8$ км.

4) Путь A — C — B (тупик, так как из B можно вернуться только в A или C, а мы их уже посетили).
Путь A — C — D также не ведет в E напрямую.

5) Путь A — D — C — E
Из A в D дорога равна $4$ км.
Из D в C дорога равна $3$ км.
Из C в E дорога равна $2$ км.
Длина пути: $4 + 3 + 2 = 9$ км.

Сравним полученные результаты:
- Путь A — B — C — E: $7$ км.
- Путь A — C — E: $8$ км.
- Путь A — D — C — E: $9$ км.

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

Ответ: 7

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