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

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

Графы

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

	A	B	C	D	E
A		3	9	8	9
B	3			4
C	9			3	2
D	8	4	3		2
E	9		2	2

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

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

Пояснение

Решение.

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

Шаг 1. Ищем кратчайший путь из $A$ в $D$ .
Выпишем все возможные варианты дорог из таблицы:
1) Прямой путь: $A \to D$ . Его длина равна $8$ .
2) Через пункт $B$ : $A \to B \to D$ . Длина: $3 + 4 = 7$ .
3) Через пункт $C$ : $A \to C \to D$ . Длина: $9 + 3 = 12$ (длиннее прямого пути).
4) Через пункты $B$ и $C$ : $A \to B \to C \to D$ . В таблице нет прямой дороги $B \to C$ , поэтому такой маршрут невозможен.
Самый короткий путь от $A$ до $D$ — это $A \to B \to D$ , его длина равна $7$ .

Шаг 2. Ищем кратчайший путь из $D$ в $E$ .
Важно помнить, что мы уже посетили пункты $A$ и $B$ , и возвращаться в них нельзя.
1) Прямой путь: $D \to E$ . Его длина равна $2$ .
2) Через пункт $C$ : $D \to C \to E$ . Длина: $3 + 2 = 5$ (длиннее прямого пути).
Самый короткий путь от $D$ до $E$ — это $D \to E$ , его длина равна $2$ .

Шаг 3. Вычисляем общую длину маршрута.
Сложим длины двух найденных участков пути:
$L = (A \to B \to D) + (D \to E)$
$L = 7 + 2 = 9$ .

Проверим, нет ли других вариантов. Если мы пойдём $A \to D$ напрямую (длина $8$ ), то кратчайший путь до $E$ всё равно будет $D \to E$ (длина $2$ ), что в сумме даст $10$ . Это больше, чем $9$ .

Ответ: 9

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