Задание 4 ОГЭ по информатике: кратчайший путь между пунктами

Задание 4 ОГЭ по информатике даёт таблицу дорог между населёнными пунктами с их длинами и просит найти длину кратчайшего пути. Таблицу превращают в схему, а затем идут от начального пункта, записывая у каждого пункта наименьшее известное расстояние до него.

Как решать

Шаг 1. Нарисуйте схему: пункты — точки, дороги — линии с подписанной длиной. Таблица симметрична: число на пересечении строки B и столбца C совпадает с числом на пересечении строки C и столбца B. Пустая клетка значит, что прямой дороги нет.

Шаг 2. Возле начального пункта напишите 0. Для каждого соседа запишите длину дороги до него.

Шаг 3. Возьмите пункт с наименьшим записанным числом, который вы ещё не обрабатывали, и пересчитайте его соседей: если через этот пункт дорога к соседу короче, чем уже записано, исправьте число. Отметьте пункт как обработанный.

Шаг 4. Повторяйте, пока не обработаете конечный пункт. Число возле него и есть ответ.

Если в условии сказано, что путь должен проходить через пункт X, найдите отдельно кратчайший путь от начала до X и от X до конца и сложите. Проверьте, что два куска не проходят через один и тот же пункт: по условию каждый пункт можно посетить только один раз.

Путь с меньшим числом дорог не обязательно короче. Задания составляют так, что обходной путь через три-четыре пункта часто выигрывает у прямой дороги.

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

Пример 1

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.

     A   B   C   D   E   F
A        3   8
B    3       2   7
C    8   2       4   9
D        7   4       2   8
E            9   2       3
F                8   3

Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.

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

# Задание 4 ОГЭ, пример 1: кратчайший путь из A в F, каждый пункт не больше одного раза
roads = {
    ("A", "B"): 3, ("A", "C"): 8, ("B", "C"): 2, ("B", "D"): 7, ("C", "D"): 4,
    ("C", "E"): 9, ("D", "E"): 2, ("D", "F"): 8, ("E", "F"): 3,
}
graph = {}
for (u, v), km in roads.items():  # дороги двусторонние
    graph.setdefault(u, {})[v] = km
    graph.setdefault(v, {})[u] = km


def paths(city, finish, visited, length):
    """Длины всех путей без повторов пунктов."""
    if city == finish:
        yield length
        return
    for nxt, km in graph[city].items():
        if nxt not in visited:
            yield from paths(nxt, finish, visited | {nxt}, length + km)


print(min(paths("A", "F", {"A"}, 0)))

Ответ: 14

От A: до B 3, до C 8. Через B до C получается 3 + 2 = 5, это меньше 8. Из C: до D 5 + 4 = 9 (через B напрямую до D было бы 3 + 7 = 10), до E 5 + 9 = 14. Из D: до E 9 + 2 = 11, до F 9 + 8 = 17. Из E: до F 11 + 3 = 14. Кратчайший путь A–B–C–D–E–F длиной 14 км проходит через все шесть пунктов.

Пример 2

Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.

     A   B   C   D   E
A        1       6
B    1       5       7
C        5       2   3
D    6       2       4
E        7   3   4

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

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

# Задание 4 ОГЭ, пример 2: кратчайший путь из A в E, который проходит через C
roads = {
    ("A", "B"): 1, ("A", "D"): 6, ("B", "C"): 5, ("B", "E"): 7,
    ("C", "D"): 2, ("C", "E"): 3, ("D", "E"): 4,
}
graph = {}
for (u, v), km in roads.items():
    graph.setdefault(u, {})[v] = km
    graph.setdefault(v, {})[u] = km


def paths(route, finish, length):
    """Все пути без повторов пунктов: список пунктов и длина."""
    city = route[-1]
    if city == finish:
        yield route, length
        return
    for nxt, km in graph[city].items():
        if nxt not in route:
            yield from paths(route + [nxt], finish, length + km)


print(min(length for route, length in paths(["A"], "E", 0) if "C" in route))

Ответ: 9

Без условия кратчайший путь — A–B–E длиной 8, но он не проходит через C. От A до C: через B 1 + 5 = 6, через D 6 + 2 = 8, выбираем 6. От C до E: напрямую 3, через D 2 + 4 = 6, выбираем 3. Путь A–B–C–E: 6 + 3 = 9 км, пункты не повторяются.

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

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

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

Можно ли проходить через один пункт дважды?

Нет. В условии задания 4 сказано, что каждый пункт можно посетить только один раз. Для кратчайшего пути это ограничение почти никогда не мешает: возвращаться в пункт невыгодно.

Нужно ли рисовать схему?

Это не обязательно, но так меньше ошибок. На схеме сразу видны обходные пути, которые в таблице легко пропустить.

Что такое весовая матрица?

Это таблица, в которой на пересечении строки и столбца стоит длина дороги между двумя пунктами. Именно такую таблицу дают в задании 4.

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

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

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

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