Задание 4 ОГЭ по информатике: решайте с автопроверкой

В задании 4 дана таблица длин дорог между пунктами. Нужно найти длину кратчайшего пути между двумя пунктами, иногда с условием: через определённый пункт, в обход него или не больше чем по k дорогам.

Решать задачи номера

Как решать программой

Для пяти-шести пунктов кратчайший путь находят руками, но легко пропустить объезд. Программа считает его алгоритмом Флойда: в таблице расстояний для каждого промежуточного пункта m путь i → m → j заменяет путь i → j, если он короче.

Таблица экзамена симметрична: по дороге можно ехать в обе стороны. Отсутствующие дороги обозначьте бесконечностью, float("inf").

Путь через пункт C — это d[A][C] + d[C][B]. Путь в обход пункта считается тем же алгоритмом, но без этого пункта в роли промежуточного.

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

Разбор примера

Пункты A, B, C, дороги AB 4, BC 3, AC 9. Какова длина кратчайшего пути из A в C?

INF = float('inf')
n = 3
roads = [(0, 1, 4), (1, 2, 3), (0, 2, 9)]
d = [[0 if i == j else INF for j in range(n)] for i in range(n)]
for u, v, w in roads:
    d[u][v] = d[v][u] = w
for m in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j], d[i][m] + d[m][j])
print(d[0][2])

Программа печатает

7

Прямая дорога из A в C длиной 9, а путь через B длиной 4 + 3 = 7. Алгоритм Флойда находит этот объезд сам.

Решить эту задачу

Задачи к заданию 4

  • Кратчайший путь по таблице дорогЛёгкаяРешать
  • Кратчайший путь через пунктЛёгкаяРешать
  • Путь в обход пунктаЛёгкаяРешать
  • Кратчайший путь не больше чем из k дорогСредняяРешать

Бесплатно и без регистрации: пишете код в браузере и проверяете его тестами (без аккаунта — несколько задач в день).

Вопросы и ответы

Зачем программа, если пунктов пять?
Она проверяет ответ, найденный руками. Объездной путь через два пункта легко пропустить.
Как обозначить, что дороги нет?
Бесконечностью float("inf"). Любая сумма с ней тоже бесконечна и не станет кратчайшей.
Как найти путь через пункт?
Сложите кратчайший путь до этого пункта и от него до цели.
Подходит ли алгоритм Дейкстры?
Да, он тоже находит кратчайший путь. Флойд проще написать и для двадцати шести пунктов работает мгновенно.