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

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

Графы

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

	A	B	C	D	E
A		5	6	10	5
B	5			4
C	6			2	7
D	10	4	2		5
E	5		7	5

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

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

Пояснение

Решение.

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

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

Шаг 1: Ищем пути из $A$ в $E$ .
Согласно таблице, из пункта $A$ можно попасть в $E$ следующими способами:
— Прямой путь: $A \to E$ длиной $5$ .
— Через $B$ : $A \to B \to E$ . Длина: $5 + 7 = 12$ .
— Через $C$ : $A \to C \to E$ . Длина: $6 + 7 = 13$ .
Самый короткий путь из $A$ в $E$ — это прямой путь $A \to E$ длиной $5$ .

Шаг 2: Ищем пути из $E$ в $D$ .
Из пункта $E$ можно попасть в $D$ следующими способами:
— Прямой путь: $E \to D$ длиной $5$ .
— Через $B$ : $E \to B \to D$ . Длина: $7 + 4 = 11$ .
— Через $C$ : $E \to C \to D$ . Длина: $7 + 2 = 9$ .
Самый короткий путь из $E$ в $D$ — это прямой путь $E \to D$ длиной $5$ .

Шаг 3: Составляем итоговый маршрут.
Соединим кратчайшие участки: $A \to E$ (длина $5$ ) и $E \to D$ (длина $5$ ).
Получаем маршрут: $A \to E \to D$ .
Общая длина пути: $5 + 5 = 10$ .
Проверяем условие: пункт $E$ посещён, каждый пункт ( $A, E, D$ ) встречается в маршруте только один раз. Условие соблюдено.

Другие варианты (например, $A \to B \to D$ или $A \to C \to D$ ) не рассматриваются как основные, так как они не проходят через обязательный пункт $E$ . Если же мы попробуем составить более сложные маршруты через $B$ или $C$ , их длина будет заведомо больше $10$ .

Ответ: 10

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