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

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

Графы

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

	A	B	C	D	E
A		7	4
B	7		2		4
C	4	2		4
D			4		4
E		4		4

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

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

Пояснение

Решение.

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

Шаг 1. Находим кратчайший путь из пункта $A$ в пункт $C$ .
Посмотрим на таблицу и выпишем возможные варианты дорог из $A$ в $C$ :
1) Прямой путь: $A \rightarrow C$ . Его длина равна $4$ км.
2) Путь через $B$ : $A \rightarrow B \rightarrow C$ . Длина: $7 + 2 = 9$ км.
Кратчайший путь из $A$ в $C$ — это прямой путь $A \rightarrow C$ длиной $4$ км.

Шаг 2. Находим кратчайший путь из пункта $C$ в пункт $E$ .
Теперь ищем дорогу из $C$ в $E$ , учитывая, что в пункте $A$ мы уже были и возвращаться туда нельзя. Возможные варианты:
1) Путь через $B$ : $C \rightarrow B \rightarrow E$ . Длина: $2 + 4 = 6$ км.
2) Путь через $D$ : $C \rightarrow D \rightarrow E$ . Длина: $4 + 4 = 8$ км.
3) Путь через $B$ и $D$ : $C \rightarrow B \rightarrow D \rightarrow E$ . Длина: $2 + 4 + 4 = 10$ км.
Кратчайший путь из $C$ в $E$ — это путь через $B$ ( $C \rightarrow B \rightarrow E$ ) длиной $6$ км.

Шаг 3. Вычисляем общую длину маршрута.
Сложим длины двух найденных участков:
$L = (A \rightarrow C) + (C \rightarrow B \rightarrow E) = 4 \text{ км} + 6 \text{ км} = 10 \text{ км}$ .

Проверим, нет ли других вариантов. Если мы пойдем $A \rightarrow B \rightarrow C$ , то кратчайший остаток пути до $E$ будет через $D$ ( $C \rightarrow D \rightarrow E$ ), так как $B$ уже посещен. Тогда длина составит $9 + 8 = 17$ км, что значительно больше.

Таким образом, кратчайший путь: $A \rightarrow C \rightarrow B \rightarrow E$ .

Ответ: 10 км

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