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

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

Графы

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

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

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

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

Пояснение

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

1. Анализ таблицы:
Из пункта A можно попасть только в пункт B (расстояние $1$ км).
Из пункта B можно попасть в A ( $1$ км), C ( $2$ км), D ( $2$ км) и E ( $7$ км).
Из пункта C можно попасть в B ( $2$ км) и E ( $3$ км).
Из пункта D можно попасть в B ( $2$ км) и E ( $4$ км).
Из пункта E можно попасть в B ( $7$ км), C ( $3$ км) и D ( $4$ км).

2. Построение и расчет путей:
Так как из A есть дорога только в B, любой путь будет начинаться с отрезка A → B.
Рассмотрим все варианты продолжения пути из точки B:

Вариант 1: Прямой путь из B в E
Путь: A → B → E
Длина: $1 + 7 = 8$ км.

Вариант 2: Путь через пункт C
Путь: A → B → C → E
Длина: $1 + 2 + 3 = 6$ км.

Вариант 3: Путь через пункт D
Путь: A → B → D → E
Длина: $1 + 2 + 4 = 7$ км.

3. Сравнение результатов:
Мы получили три возможных маршрута:
- A → B → E: $8$ км;
- A → B → C → E: $6$ км;
- A → B → D → E: $7$ км.

Самым коротким является путь через пункт C, его длина составляет $6$ км.

Ответ: 6 км

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