Решение. Для решения этой задачи мы воспользуемся методом динамического программирования. Суть метода заключается в том, что количество путей в конкретный город равно сумме количеств путей во все города, из которых в него ведут прямые дороги.

Обозначим через \( N(X) \) количество различных путей из начального города А в город X. Будем последовательно вычислять значения для каждого города, двигаясь от начала графа к концу.

1. Начнём с исходного пункта. В город А существует только один путь (начальная точка):
\( N(A) = 1 \)

2. Найдём количество путей в города, в которые можно попасть напрямую из А:
В город Б ведёт только одна стрелка из А:
\( N(Б) = N(A) = 1 \)
В город Г ведёт только одна стрелка из А:
\( N(Г) = N(A) = 1 \)

3. Теперь рассмотрим город В. В него ведут дороги из Б, А и Г:
\( N(В) = N(Б) + N(A) + N(Г) = 1 + 1 + 1 = 3 \)

4. Перейдём к городу Д. В него можно попасть только из города Г:
\( N(Д) = N(Г) = 1 \)

5. Рассмотрим город Е. В него ведут дороги из В и Д:
\( N(Е) = N(В) + N(Д) = 3 + 1 = 4 \)

6. Наконец, вычислим количество путей в финальный пункт — город К. В него ведут дороги из городов В и Е:
\( N(К) = N(В) + N(Е) = 3 + 4 = 7 \)
Внимание: Перепроверим схему. В город К ведут стрелки из В, Е и Д.
Уточним расчёт для К: \( N(К) = N(В) + N(Е) + N(Д) \).
Подставим значения: \( N(К) = 3 + 4 + 1 = 8 \).

Таким образом, существует 8 различных путей из города А в город К.

Ответ: 8

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

ОГЭ Информатика