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

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

Графы

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

	A	B	C	D	E
A		2			5
B	2		2	3	1
C		2		1
D		3	1		1
E	5	1		1

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

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

Пояснение

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

Проанализируем таблицу и выпишем все возможные маршруты:

1. Прямой путь A — D:
Согласно таблице, на пересечении строки $A$ и столбца $D$ стоит число $5$ .
Длина пути: $5$ км.

2. Путь через пункт B:
Из $A$ в $B$ расстояние равно $2$ . Из $B$ можно пойти в $D$ напрямую или через другие пункты.
• A — B — D: $2 + 3 = 5$ км.
• A — B — C — D: $2 + 2 + 1 = 5$ км.
• A — B — E — D: $2 + 1 + 1 = 4$ км.

3. Путь через пункт E (если бы мы пошли из A в E напрямую):
В таблице нет прямой дороги между $A$ и $E$ , поэтому такой вариант невозможен.

4. Проверим другие комбинации, чтобы убедиться, что мы ничего не упустили:
• A — B — C — E — D: $2 + 2 + 1 + 1 = 6$ км (это длиннее уже найденного пути).
• A — B — D: мы уже посчитали, это $5$ км.

Сравним полученные результаты:
Путь $A-D$ : $5$ км.
Путь $A-B-D$ : $5$ км.
Путь $A-B-C-D$ : $5$ км.
Путь $A-B-E-D$ : $4$ км.

Самым коротким оказался путь A — B — E — D, его протяжённость составляет $4$ км.

Ответ: 4

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