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

Дана матрица смежности, отображающая расстояние между городами. Найдите кратчайший путь между городами А и 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$$.