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

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

Графы

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

	A	B	C	D	E
A		1	5		2
B	1			6
C	5			1	7
D		6	1
E	2		7

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

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

Пояснение

Решение.

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

Разобьём задачу на два этапа:
1. Найдём кратчайший путь из $A$ в $B$ .
2. Найдём кратчайший путь из $B$ в $D$ , не заходя повторно в пункт $A$ .

Шаг 1: Путь из A в B.
Посмотрим на таблицу. Прямая дорога из $A$ в $B$ существует и её длина равна $1$ .
Проверим, есть ли более короткие пути через другие пункты:
- Через $C$ : $A \to C \to B$ — дороги $C \to B$ нет.
- Через $E$ : $A \to E \to B$ — дороги $E \to B$ нет.
Следовательно, кратчайший путь $A \to B$ равен $1$ .

Шаг 2: Путь из B в D.
Теперь нам нужно попасть из $B$ в $D$ . По условию мы уже были в пункте $A$ , поэтому возвращаться в него нельзя.
Рассмотрим возможные варианты из таблицы для пункта $B$ :
1. Прямой путь $B \to D$ . Согласно таблице, длина этой дороги равна $6$ .
2. Путь через пункт $C$ : $B \to C \to D$ . Однако прямой дороги из $B$ в $C$ в таблице нет (ячейка пуста).
3. Путь через пункт $E$ : $B \to E$ . Но дороги из $B$ в $E$ также нет.
Таким образом, единственный возможный путь из $B$ в $D$ , не проходящий через $A$ , — это прямая дорога $B \to D$ длиной $6$ .

Шаг 3: Итоговый расчет.
Сложим длины найденных участков пути:
$L = (A \to B) + (B \to D)$
$L = 1 + 6 = 7$

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

Ответ: 7

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