Подсчет путей в графе: решение задачи из информатики

Задание 1

Условие: На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G, H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город H?

Решение:

Это задача на подсчет количества путей в ориентированном графе. Решать будем методом "динамического программирования", последовательно подсчитывая количество путей до каждого города.

1. Город A: Из города A можно только выехать, поэтому количество путей до него равно 1 (сам город).

   • Путей до A: 1

2. Города B и C: Из A есть прямой путь только в B и C.

   • Путей до B: 1 (A -> B)
   • Путей до C: 1 (A -> C)

3. Город D: В город D можно попасть из B и C.

   • Путей до D = (Путей до B) + (Путей до C) = 1 + 1 = 2
   • Пути: A -> B -> D, A -> C -> D

4. Город E: В город E можно попасть из B и D.

   • Путей до E = (Путей до B) + (Путей до D) = 1 + 2 = 3
   • Пути: A -> B -> E, A -> B -> D -> E, A -> C -> D -> E

5. Город G: В город G можно попасть из D и E.

   • Путей до G = (Путей до D) + (Путей до E) = 2 + 3 = 5
   • Пути: A -> B -> D -> G, A -> C -> D -> G, A -> B -> E -> G, A -> B -> D -> E -> G, A -> C -> D -> E -> G

6. Город F: В город F можно попасть только из C.

   • Путей до F = (Путей до C) = 1
   • Путь: A -> C -> F

7. Город H: В город H можно попасть из G и F.

   • Путей до H = (Путей до G) + (Путей до F) = 5 + 1 = 6
   • Пути: A -> B -> D -> G -> H, A -> C -> D -> G -> H, A -> B -> E -> G -> H, A -> B -> D -> E -> G -> H, A -> C -> D -> E -> G -> H, A -> C -> F -> H

Итого: Всего существует 6 различных путей из города A в город H.

Ответ: 6