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

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

Графы

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

	A	B	C	D	Е
A		1	1		4
B	1			3	3
C	1			2	1
D		3	2		5
Е	4	3	1	5

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

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

Пояснение

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

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

1. Прямой путь или через один промежуточный пункт:
- $A \rightarrow E$ : длина $4$ км.
- $A \rightarrow B \rightarrow E$ : длина $1 + 3 = 4$ км.
- $A \rightarrow C \rightarrow E$ : длина $1 + 1 = 2$ км.

2. Пути через два промежуточных пункта:
- $A \rightarrow B \rightarrow C \rightarrow E$ : длина $1 + 3 + 1 = 5$ км.
- $A \rightarrow B \rightarrow D \rightarrow E$ : длина $1 + 3 + 5 = 9$ км.
- $A \rightarrow C \rightarrow B \rightarrow E$ : длина $1 + 3 + 3 = 7$ км.
- $A \rightarrow C \rightarrow D \rightarrow E$ : длина $1 + 2 + 5 = 8$ км.
- $A \rightarrow D \rightarrow C \rightarrow E$ : длина $4 + 2 + 1 = 7$ км.
- $A \rightarrow D \rightarrow B \rightarrow E$ : длина $4 + 3 + 3 = 10$ км.

3. Пути через три промежуточных пункта:
- $A \rightarrow B \rightarrow C \rightarrow D \rightarrow E$ : длина $1 + 3 + 2 + 5 = 11$ км.
- $A \rightarrow D \rightarrow C \rightarrow B \rightarrow E$ : длина $4 + 2 + 3 + 3 = 12$ км.

Сравним полученные результаты. Самым коротким оказался путь $A \rightarrow C \rightarrow E$ , протяжённость которого составляет $2$ км.

Ответ: 2

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