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

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

Графы

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

	A	B	C	D	E
A		3	3
B	3			5	6
C	3			4
D		5	4		1
E		6		1

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

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

Пояснение

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

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

1) Путь A — B — E.
Из пункта A можно попасть в B (длина $3$ ). Из пункта B есть прямая дорога в E (длина $6$ ).
Длина пути: $3 + 6 = 9$ км.

2) Путь A — B — C — D — E.
Из A в B (длина $3$ ), из B в C (длина $5$ ), из C в D (длина $4$ ), из D в E (длина $1$ ).
Длина пути: $3 + 5 + 4 + 1 = 13$ км.

3) Путь A — B — D — E.
Из A в B (длина $3$ ), из B в D (длина $4$ ), из D в E (длина $1$ ).
Длина пути: $3 + 4 + 1 = 8$ км.

4) Путь A — C — B — E.
Из A в C (длина $3$ ), из C в B (длина $5$ ), из B в E (длина $6$ ).
Длина пути: $3 + 5 + 6 = 14$ км.

5) Путь A — C — D — E.
Из A в C (длина $3$ ), из C в D (длина $4$ ), из D в E (длина $1$ ).
Длина пути: $3 + 4 + 1 = 8$ км.

6) Путь A — C — B — D — E.
Из A в C (длина $3$ ), из C в B (длина $5$ ), из B в D (длина $4$ ), из D в E (длина $1$ ).
Длина пути: $3 + 5 + 4 + 1 = 13$ км.

Сравним полученные результаты: $9$ , $13$ , $8$ , $14$ , $8$ , $13$ . Минимальное значение равно $8$ .

Ответ: 8 км

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