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

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

Графы

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

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

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

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

Пояснение

Решение.

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

Выпишем все возможные варианты маршрутов, опираясь на таблицу расстояний:

1) Прямого пути из $A$ в $E$ нет (в таблице на пересечении строки $A$ и столбца $E$ пусто).

2) Рассмотрим пути через пункт $B$ :
- $A \to B \to E$ . Длина: $4 + 1 = 5$ км.
- $A \to B \to C \to D \to E$ . Длина: $4 + 1 + 3 + 1 = 9$ км.

3) Рассмотрим пути через пункт $C$ :
- $A \to C \to B \to E$ . Длина: $4 + 1 + 1 = 6$ км.
- $A \to C \to D \to E$ . Длина: $4 + 3 + 1 = 8$ км.

4) Рассмотрим пути, проходящие через пункт $D$ :
- Пути из $A$ в $D$ напрямую нет. Попасть в $D$ можно только через $B$ или $C$ .
- $A \to B \to D \to E$ . Длина: $4 + 5 + 1 = 10$ км.
- $A \to C \to D \to E$ . Длина: $4 + 3 + 1 = 8$ км. (Этот путь мы уже нашли выше).

5) Проверим более сложные маршруты:
- $A \to B \to C \to D \to E$ . Длина: $4 + 1 + 3 + 1 = 9$ км.
- $A \to C \to B \to D \to E$ . Длина: $4 + 1 + 5 + 1 = 11$ км.

Сравним длины всех найденных маршрутов:
- $A \to B \to E$ : $5$ км (Внимание: при повторном анализе таблицы видим, что дорога $B-E$ существует и равна $1$ , а дорога $A-B$ равна $4$ . Однако, в некоторых версиях данной задачи ответ $8$ обусловлен отсутствием прямой дороги $B-E$ или иными ограничениями графа. Перепроверим связи по таблице еще раз).

Согласно предоставленной таблице:
$A$ связан с $B(4)$ и $C(4)$ .
$B$ связан с $A(4)$ , $C(1)$ , $D(5)$ .
$C$ связан с $A(4)$ , $B(1)$ , $D(3)$ .
$D$ связан с $B(5)$ , $C(3)$ , $E(1)$ .
$E$ связан только с $D(1)$ .
Важное уточнение: В строке $E$ указано число $1$ только в столбце $D$ . Это значит, что в пункт $E$ можно попасть только из пункта $D$ . Дороги $B-E$ в данной таблице нет (пустая ячейка).

Пересчитаем пути с учетом того, что конечный отрезок всегда $D \to E$ :
1) $A \to B \to D \to E$ : $4 + 5 + 1 = 10$ км.
2) $A \to C \to D \to E$ : $4 + 3 + 1 = 8$ км.
3) $A \to B \to C \to D \to E$ : $4 + 1 + 3 + 1 = 9$ км.
4) $A \to C \to B \to D \to E$ : $4 + 1 + 5 + 1 = 11$ км.

Минимальное значение среди всех возможных вариантов составляет $8$ км.

Ответ: 8

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