ОГЭ · краткий ответ

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

Что проверяет номер, типичные ошибки, пример с решением на Python и 10 заданий с ответами под спойлером.

91задание в банке
с ответамикак в КИМ
1 кликзадание на доске

Что проверяет задание 4 ОГЭ

Между населёнными пунктами построены дороги, их протяжённость (стоимость) дана в таблице. Двигаться можно только по дорогам из таблицы. Нужно найти длину кратчайшего пути из одного пункта в другой. Удобно нарисовать граф и последовательно находить кратчайшие расстояния до всех пунктов (алгоритм Дейкстры на бумаге).

ОГЭ, задание 491 задание в банке ИнфДоски

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

  • Берут прямую дорогу, не проверив обходные пути — они часто короче.
  • Читают таблицу только по строкам и пропускают дороги из столбцов.
  • Проходят через запрещённый пункт, если в условии есть ограничение.
  • Складывают длины не на одном пути, а по разным веткам.

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

Условие

Дороги и их длины: А–Б 2, А–В 5, Б–В 1, Б–Г 7, В–Г 2, В–Д 6, Г–Д 1, Г–Е 5, Д–Е 2. Определите длину кратчайшего пути из А в Е.

Решение

До Б — 2, до В — 2 + 1 = 3 (короче прямой 5), до Г — 3 + 2 = 5, до Д — 5 + 1 = 6 (короче, чем 3 + 6), до Е — 6 + 2 = 8 (короче, чем 5 + 5). Ответ: 8, путь А–Б–В–Г–Д–Е.

import heapq
roads = {('А', 'Б'): 2, ('А', 'В'): 5, ('Б', 'В'): 1, ('Б', 'Г'): 7, ('В', 'Г'): 2,
         ('В', 'Д'): 6, ('Г', 'Д'): 1, ('Г', 'Е'): 5, ('Д', 'Е'): 2}
g = {}
for (a, b), w in roads.items():
    g.setdefault(a, []).append((b, w))
    g.setdefault(b, []).append((a, w))
dist, q = {'А': 0}, [(0, 'А')]
while q:
    d, v = heapq.heappop(q)
    for u, w in g[v]:
        if d + w < dist.get(u, 10**9):
            dist[u] = d + w
            heapq.heappush(q, (d + w, u))
print(dist['Е'])
Код на Python 3 — его можно запустить прямо на ИнфДоске.
Ответ: 8

Задания из банка

В банке ИнфДоски 91 задание этого номера. Ниже — 10 из них, ответ спрятан под спойлером. Кнопка «Открыть на доске» ставит задание на вашу ИнфДоску.

Задание 1 Кратчайший путь Открыть на доске →

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

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

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

Ответ
7
Задание 2 Кратчайший путь Открыть на доске →

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

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

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

Ответ
8
Задание 3 Кратчайший путь Открыть на доске →

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

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

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

Ответ
4
Задание 4 Кратчайший путь Открыть на доске →

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

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

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

Ответ
2
Задание 5 Кратчайший путь Открыть на доске →

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

A B C D E F
A 1 5 15
B 1 2
C 5 2 3
D 3 2 3
E 2 2
F 15 3 2

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

Ответ
9
Задание 6 Кратчайший путь Открыть на доске →

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

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

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

Ответ
6
Задание 7 Кратчайший путь Открыть на доске →

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

A B C D E
A 5 8 8 12
B 5 4
C 8 7
D 8 4 5
E 12 7 5

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

Ответ
12
Задание 8 Кратчайший путь Открыть на доске →

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

A B C D E F
A 3 1 2 6
B 3 1
C 1 1
D 2 2
E 6 2 3
F 3

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

Ответ
9
Задание 9 Кратчайший путь Открыть на доске →

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

A B C D E
A 1 2
B 1 1 2
C 2 1
D 1 2
E 2 2 1

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

Ответ
3
Задание 10 Кратчайший путь Открыть на доске →

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

A B C D E F
A 3 5 15
B 3 1
C 5 1 1
D 1 2 6
E 2 2
F 15 6 2

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

Ответ
9
ИнфДоска

Разбирайте задание 4 ОГЭ на онлайн-доске

Задание из банка — на доску в один клик, ответ видите только вы. После урока доска сама составит отчёт маме или папе.

Другие задания ОГЭ