Задание 18 Параграф 10 ГДЗ Босова 11 класс (Информатика)

1. Найдите кратчайший путь от вершины А до вершины F в ориентированном графе.

По рисунку составим возможные пути из вершины A в вершину F и найдём их длины:

• $$A \to C \to F: \; 4 + 10 = 14$$
• $$A \to C \to D \to F: \; 4 + 2 + 1 = 7$$
• $$A \to B \to D \to F: \; 8 + 6 + 1 = 15$$
• $$A \to B \to E \to F: \; 8 + 3 + 4 = 15$$
• $$A \to C \to D \to E \to F: \; 4 + 2 + 3 + 4 = 13$$

Наименьшая длина получается у пути $$A \to C \to D \to F$$.

Ответ

Кратчайший путь: $$ACDF$$, его длина равна $$7$$.