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

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

Выпишем все возможные связи (дороги) и их длины из таблицы:
$A-B: 3$
$A-C: 4$
$A-F: 18$
$B-C: 3$
$C-D: 4$
$D-E: 2$
$D-F: 6$
$E-F: 1$

Теперь рассмотрим возможные маршруты из пункта $A$ в пункт $F$:

1) Прямой путь:
$A \rightarrow F$. Длина = $18$ км.

2) Пути через пункт $B$:
Так как из $B$ можно попасть только в $A$ и $C$, маршрут будет выглядеть так:
$A \rightarrow B \rightarrow C \rightarrow ...$
Длина участка $A \rightarrow B \rightarrow C$ равна $3 + 3 = 6$ км. Это длиннее, чем прямой путь $A \rightarrow C$ ($4$ км), поэтому пути через $B$ рассматривать нецелесообразно, если есть возможность пойти через $C$ напрямую.

3) Пути через пункт $C$:
Из $C$ можно пойти в $D$ (путь в $B$ мы уже обсудили как невыгодный):
$A \rightarrow C \rightarrow D$. Длина = $4 + 4 = 8$ км.
Далее из $D$ есть два варианта попасть в $F$:
а) Напрямую: $A \rightarrow C \rightarrow D \rightarrow F$. Длина = $8 + 6 = 14$ км.
б) Через пункт $E$: $A \rightarrow C \rightarrow D \rightarrow E \rightarrow F$. Длина = $8 + 2 + 1 = 11$ км.

4) Проверим вариант с заездом в $B$, если идти через $C$:
$A \rightarrow B \rightarrow C \rightarrow D \rightarrow E \rightarrow F$. Длина = $3 + 3 + 4 + 2 + 1 = 13$ км. Это длиннее, чем $11$ км.

Сравним полученные результаты:
- $A \rightarrow F$: $18$ км
- $A \rightarrow C \rightarrow D \rightarrow F$: $14$ км
- $A \rightarrow B \rightarrow C \rightarrow D \rightarrow E \rightarrow F$: $13$ км
- $A \rightarrow C \rightarrow D \rightarrow E \rightarrow F$: $11$ км

Самым коротким оказался путь $A \rightarrow C \rightarrow D \rightarrow E \rightarrow F$ протяженностью $11$ км.

Ответ: 11 км

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