Задание 6 Параграф 14 ГДЗ Семакин 9 класс (Информатика)

Найдите кратчайший путь между городами А н F.
Пути из А в F:
A > F=14
A > D > F=8+3=11
A > C > D > F=4+3+3=10
Кратчайший путь A > C > D > F

Рассмотрим возможные пути из города $$A$$ в город $$F$$ по матрице смежности:

• $$A \to F = 14$$
• $$A \to D \to F = 8 + 3 = 11$$
• $$A \to C \to D \to F = 4 + 3 + 3 = 10$$

Сравним полученные длины путей: $$14$$, $$11$$ и $$10$$. Наименьшая длина равна $$10$$.

Значит, кратчайший путь проходит через города $$A \to C \to D \to F$$.

Ответ

$$A \to C \to D \to F$$, длина пути $$10$$.