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

В задании №4 ОГЭ по информатике нужно найти длину кратчайшего пути между пунктами по таблице дорог. Обычно дана таблица с расстояниями между городами или пунктами, а нужно определить самый короткий маршрут.

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

В задании №4 проверяют, умеет ли ученик:

• читать таблицу расстояний;
• понимать, между какими пунктами есть дороги;
• находить возможные маршруты;
• складывать длины дорог;
• выбирать кратчайший путь;
• учитывать дополнительные условия задачи.

Чаще всего нужно найти кратчайший путь между двумя пунктами, например от A до E.

Как устроена таблица дорог

В задаче обычно дана таблица.

Например:

Число в таблице показывает длину дороги между двумя пунктами.

Например:

A — B = 7
A — C = 4
B — C = 2
B — E = 5
C — D = 4
D — E = 5

Если клетка пустая, значит прямой дороги между пунктами нет.

Важное правило

Таблица обычно симметричная.

Если есть дорога:

A — B = 7

то это значит, что можно ехать и так:

A → B

и так:

B → A

Длина дороги в обоих направлениях одинаковая.

Что такое граф

Такую задачу удобно представлять как граф.

Граф — это схема, где:

• пункты — это вершины;
• дороги — это рёбра;
• числа на дорогах — это длины рёбер.

Например, если в таблице есть:

A — C = 4

то на схеме можно нарисовать дорогу от A к C длиной 4.

Главная идея решения

Чтобы найти кратчайший путь, нужно:

1. Выписать все дороги из таблицы.
2. Найти возможные маршруты от начального пункта к конечному.
3. Посчитать длину каждого маршрута.
4. Выбрать самый короткий.

Пример 1. Кратчайший путь от A до E

Условие

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

Определите длину кратчайшего пути между пунктами A и E.

Шаг 1. Выпишем дороги

По таблице видим дороги:

A — B = 7
A — C = 4
B — C = 2
B — E = 5
C — D = 4
D — E = 5

Шаг 2. Найдём возможные пути от A до E

Из пункта A можно пойти в B или C.

Рассмотрим основные маршруты.

Первый путь:

A → B → E

Длина:

7 + 5 = 12

Второй путь:

A → C → D → E

Длина:

4 + 4 + 5 = 13

Третий путь:

A → C → B → E

Длина:

4 + 2 + 5 = 11

Шаг 3. Выбираем кратчайший путь

Сравним длины:

Самый короткий путь:

A → C → B → E

Его длина:

11

Ответ

11

Как не пропустить короткий путь

Иногда кажется, что самый короткий путь — тот, где меньше дорог.

Но это не всегда так.

Например:

A → B → E

имеет всего 2 дороги, но длина:

7 + 5 = 12

А путь:

A → C → B → E

имеет 3 дороги, но длина:

4 + 2 + 5 = 11

Он длиннее по количеству переходов, но короче по расстоянию.

Задачи с обязательным пунктом

Иногда в задании сказано, что путь должен проходить через определённый пункт.

Например:

Найдите кратчайший путь от A до E, проходящий через пункт C.

Это значит, что маршрут обязательно должен содержать пункт C.

Пример 2. Кратчайший путь через пункт C

Условие

Дана таблица дорог:

Определите длину кратчайшего пути между пунктами A и E, проходящего через пункт C.

Два раза посещать один пункт нельзя.

Шаг 1. Выпишем дороги

Из таблицы получаем:

A — B = 1
A — C = 4
A — D = 3
A — E = 7
B — C = 2
B — D = 5
C — D = 3
D — E = 2

Шаг 2. Помним условие

Путь должен:

• начинаться в A;
• заканчиваться в E;
• обязательно проходить через C;
• не посещать один пункт два раза.

Шаг 3. Проверим возможные маршруты

Первый путь:

A → C → D → E

Длина:

4 + 3 + 2 = 9

Второй путь:

A → B → C → D → E

Длина:

1 + 2 + 3 + 2 = 8

Третий путь:

A → C → B → D → E

Длина:

4 + 2 + 5 + 2 = 13

Шаг 4. Выбираем кратчайший

Сравним:

Самый короткий путь:

A → B → C → D → E

Его длина:

8

Ответ

8

Что значит "два раза посещать один пункт нельзя"

Это означает, что маршрут не должен возвращаться в уже посещённый пункт.

Например, путь:

A → B → C → B → E

нельзя использовать, потому что пункт B встречается два раза.

Если в условии есть такое ограничение, нужно проверять маршрут особенно внимательно.

Задачи без обязательного пункта

Если в задаче просто сказано:

Найдите кратчайший путь от A до E.

То можно использовать любой маршрут, главное — чтобы он был самым коротким.

Например, можно идти:

A → B → E

или:

A → C → B → E

или:

A → C → D → E

Нужно сравнить длины и выбрать минимум.

Задачи с обязательным пунктом

Если сказано:

Путь должен проходить через пункт C.

То нельзя брать путь, где C не встречается.

Например, если путь:

A → D → E

очень короткий, но в нём нет пункта C, он не подходит.

Как решать задание 4 ОГЭ по информатике

Используй такой алгоритм:

1. Посмотри на таблицу.
2. Выпиши все дороги.
3. Определи начальный и конечный пункты.
4. Проверь, есть ли дополнительные условия.
5. Найди несколько возможных маршрутов.
6. Посчитай длину каждого маршрута.
7. Отбрось маршруты, которые нарушают условие.
8. Выбери самый короткий путь.

Удобный способ через список дорог

Чтобы не запутаться в таблице, удобно сначала выписать все дороги отдельно.

Например, из таблицы:

получаем:

A — B = 5
A — C = 2
B — C = 1

Так маршруты искать намного проще.

Удобный способ через точки

Можно рисовать небольшую схему.

Например:

A — 7 — B — 5 — E
|       |
4       2
|       |
C — 4 — D — 5 — E

Даже простая схема помогает быстрее увидеть возможные пути.

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

Ошибка 1. Считают путь по количеству дорог

Кратчайший путь — это не тот, где меньше переходов, а тот, где меньше сумма расстояний.

Например:

A → B → E = 12

а:

A → C → B → E = 11

Значит, второй путь короче, хотя в нём больше переходов.

Ошибка 2. Используют несуществующую дорогу

Если в таблице клетка пустая, дороги между этими пунктами нет.

Например, если в таблице нет дороги:

C — E

то путь:

A → C → E

использовать нельзя.

Ошибка 3. Забывают обязательный пункт

Если сказано, что путь должен проходить через C, то все маршруты без C не подходят.

Ошибка 4. Посещают один пункт два раза

Если в условии сказано, что два раза посещать один пункт нельзя, маршрут с повтором пункта запрещён.

Ошибка 5. Не проверяют альтернативные маршруты

Иногда очевидный путь не самый короткий.

Нужно проверить хотя бы несколько вариантов.

Мини-практика

Задание 1

Даны дороги:

A — B = 6
A — C = 2
B — D = 3
C — D = 5
D — E = 4
B — E = 10

Найдите длину кратчайшего пути от A до E.

Задание 2

Даны дороги:

A — B = 2
A — C = 5
B — C = 1
B — D = 4
C — E = 7
D — E = 3

Найдите длину кратчайшего пути от A до E, проходящего через пункт C.

Задание 3

Даны дороги:

A — B = 4
A — C = 8
B — C = 2
B — D = 7
C — D = 1
D — E = 3

Найдите длину кратчайшего пути от A до E.

Задание 4

Даны дороги:

A — B = 3
A — C = 6
B — D = 4
C — D = 2
D — E = 5
B — E = 12

Найдите длину кратчайшего пути от A до E, проходящего через пункт D.

Ответы

Ответ 1

Проверим пути:

A → B → E = 6 + 10 = 16

A → B → D → E = 6 + 3 + 4 = 13

A → C → D → E = 2 + 5 + 4 = 11

Кратчайший путь:

A → C → D → E

Ответ:

11

Ответ 2

Путь должен проходить через C.

Проверим варианты:

A → C → E = 5 + 7 = 12

A → B → C → E = 2 + 1 + 7 = 10

A → C → B → D → E = 5 + 1 + 4 + 3 = 13

Кратчайший путь:

A → B → C → E

Ответ:

10

Ответ 3

Проверим пути:

A → B → D → E = 4 + 7 + 3 = 14

A → B → C → D → E = 4 + 2 + 1 + 3 = 10

A → C → D → E = 8 + 1 + 3 = 12

Кратчайший путь:

A → B → C → D → E

Ответ:

10

Ответ 4

Путь должен проходить через D.

Проверим варианты:

A → B → D → E = 3 + 4 + 5 = 12

A → C → D → E = 6 + 2 + 5 = 13

Кратчайший путь:

A → B → D → E

Ответ:

12

Итог

Задание №4 ОГЭ по информатике связано с поиском кратчайшего пути по таблице дорог.

Главное, что нужно уметь:

• читать таблицу расстояний;
• понимать, где есть дорога, а где её нет;
• выписывать возможные маршруты;
• складывать длины дорог;
• учитывать дополнительные условия;
• выбирать минимальную сумму.

Кратчайший путь — это путь с наименьшей суммой расстояний, а не обязательно путь с наименьшим количеством переходов.