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

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

Графы

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

	A	B	C	D	E
A		3	5
B	3		1	6
C	5	1		4	1
D		6	4		3
E			1	3

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

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

Пояснение

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

Выпишем все возможные пути из $A$ в $D$ , учитывая условие, что каждый пункт можно посетить только один раз:

1) Прямого пути из $A$ в $D$ нет (в таблице на пересечении строки $A$ и столбца $D$ пусто).

2) Пути через пункт $B$ :
— $A \to B \to C \to D$ . Длина: $3 + 1 + 4 = 8$ .
— $A \to B \to C \to E \to D$ . Длина: $3 + 1 + 1 + 3 = 8$ .
— $A \to B \to D$ . Длина: $3 + 6 = 9$ .

3) Пути через пункт $C$ :
— $A \to C \to D$ . Длина: $5 + 4 = 9$ .
— $A \to C \to B \to D$ . Длина: $5 + 1 + 6 = 12$ .
— $A \to C \to E \to D$ . Длина: $5 + 1 + 3 = 9$ .

Сравним полученные результаты:
Путь $A-B-C-D$ имеет длину $8$ .
Путь $A-B-C-E-D$ имеет длину $8$ .
Путь $A-B-D$ имеет длину $9$ .
Путь $A-C-D$ имеет длину $9$ .
Путь $A-C-E-D$ имеет длину $9$ .
Путь $A-C-B-D$ имеет длину $12$ .

Минимальное значение среди всех возможных вариантов равно $8$ .

Ответ: 8

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