Задание 9 ОГЭ по информатике: сколько путей из одного города в другой

Задание 9 ОГЭ по информатике даёт схему дорог между городами, по каждой дороге можно ехать только в одну сторону. Нужно посчитать, сколько существует различных путей из одного города в другой. Для каждого города записывают число путей до него: оно равно сумме чисел у городов, из которых в него ведут дороги.

Как решать

На экзамене схема дана рисунком. Ниже в примерах те же дороги записаны списком: запись A → B значит, что из A в B можно проехать, а обратно нельзя.

Шаг 1. Возле начального города напишите 1: до него ведёт один путь — никуда не ехать.

Шаг 2. Возьмите город, у которого все входящие дороги идут из уже подписанных городов. Число путей до него равно сумме чисел у этих городов. Например, если в C ведут дороги из A, B и D, то C = A + B + D.

Шаг 3. Повторяйте, пока не дойдёте до конечного города. Его число и есть ответ.

Порядок важен: нельзя считать город, пока не посчитаны все города, из которых в него ведут стрелки.

Если путь должен проходить через город X, посчитайте число путей от начала до X, затем отдельно от X до конца (возле X снова ставится 1) и перемножьте. Если путь не должен проходить через X, считайте как обычно, но дороги, выходящие из X, не учитывайте: поставьте возле X ноль.

Примеры с решением

Пример 1

Схема дорог связывает города A, B, C, D, E, F, G. По каждой дороге можно двигаться только в одном направлении:

A → B, A → C, A → D,
B → C, B → E,
C → E, C → F,
D → C, D → F,
E → F, E → G,
F → G

Сколько существует различных путей из города A в город G?

Проверка ответа на Python

# Задание 9 ОГЭ, пример 1: число путей из A в G по односторонним дорогам
from functools import lru_cache

roads = "AB AC AD BC BE CE CF DC DF EF EG FG".split()
nxt = {}
for r in roads:
    nxt.setdefault(r[0], []).append(r[1])


@lru_cache(None)
def count(city, finish):
    """Сколько путей ведёт из city в finish."""
    if city == finish:
        return 1
    return sum(count(n, finish) for n in nxt.get(city, []))


print(count("A", "G"))

Ответ: 12

A = 1. B: дорога только из A, B = 1. D: только из A, D = 1. C: из A, B, D, C = 1 + 1 + 1 = 3. E: из B и C, E = 1 + 3 = 4. F: из C, D, E, F = 3 + 1 + 4 = 8. G: из E и F, G = 4 + 8 = 12.

Пример 2

Схема дорог связывает города A, B, C, D, E, F, G, H, K. По каждой дороге можно двигаться только в одном направлении:

A → B, A → C, A → D,
B → E,
C → B, C → E, C → F,
D → F,
E → G, E → H,
F → E, F → H, F → K,
G → K,
H → K

Сколько существует различных путей из города A в город K, проходящих через город F?

Проверка ответа на Python

# Задание 9 ОГЭ, пример 2: пути из A в K, проходящие через F: (A -> F) * (F -> K)
from functools import lru_cache

roads = "AB AC AD BE CB CE CF DF EG EH FE FH FK GK HK".split()
nxt = {}
for r in roads:
    nxt.setdefault(r[0], []).append(r[1])


@lru_cache(None)
def count(city, finish):
    if city == finish:
        return 1
    return sum(count(n, finish) for n in nxt.get(city, []))


print(count("A", "F") * count("F", "K"))

Ответ: 8

От A до F: в F ведут дороги из C и D, а в C и D — только из A. Значит, путей до F два: A–C–F и A–D–F. От F до K (возле F ставим 1): E = 1 (только из F), G = E = 1, H = E + F = 2, K = F + G + H = 1 + 1 + 2 = 4. Всего 2 · 4 = 8 путей.

Пример 3

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

A → B, A → C, A → D,
B → E, B → F,
C → B, C → F,
D → C, D → G,
E → H,
F → E, F → G, F → H,
G → H

Сколько существует различных путей из города A в город H, не проходящих через город E?

Проверка ответа на Python

# Задание 9 ОГЭ, пример 3: пути из A в H, не проходящие через город E
from functools import lru_cache

roads = "AB AC AD BE BF CB CF DC DG EH FE FG FH GH".split()
nxt = {}
for r in roads:
    nxt.setdefault(r[0], []).append(r[1])


@lru_cache(None)
def count(city, finish):
    if city == "E":  # через E ехать нельзя
        return 0
    if city == finish:
        return 1
    return sum(count(n, finish) for n in nxt.get(city, []))


print(count("A", "H"))

Ответ: 11

Возле E ставим 0: пути через него не считаются. A = 1, D = 1 (только из A), C = A + D = 2, B = A + C = 3, F = B + C = 5, G = D + F = 6, H = E + F + G = 0 + 5 + 6 = 11.

Типичные ошибки

Потренироваться на тренажёре

Частые вопросы

Почему числа путей складываются?

Каждый путь в город C приходит по одной из входящих дорог. Пути через разные дороги разные, поэтому общее число — сумма путей до городов, из которых эти дороги выходят.

Как решать задание 9 с условием «через город»?

Разбейте путь на две части: от начала до этого города и от него до конца. Число путей в каждой части посчитайте отдельно и перемножьте: любой путь первой части можно продолжить любым путём второй.

Можно ли просто выписать все пути?

При пяти-шести путях можно, но при десяти и больше легко пропустить один. Способ с подписыванием чисел у городов надёжнее и быстрее.

Официальные материалы

Другие задания

Все задания и структура экзамена — на странице ОГЭ по информатике. Соседние разборы: задание 8 и задание 10.

Описание задания сверено 28 сентября 2026 года со спецификацией 2027 года (документы 2027 года). Примеры составлены нами по структуре демоверсии, каждое решение запущено, и напечатанный им ответ совпадает с ответом на странице. Кодолимп не связан с разработчиками экзамена. Заметили неточность — напишите нам.