Кратчайший путь в графе
Коротко
Дана таблица расстояний между пунктами (весовая матрица). Нужно найти длину кратчайшего пути. Нарисуйте граф по таблице и перебирайте пути, записывая минимальное расстояние до каждой вершины от старта (как алгоритм Дейкстры вручную).
Главное
| Шаг | Действие |
|---|---|
| 1 | построить граф по таблице |
| 2 | отметить старт расстоянием 0 |
| 3 | для соседей записать минимум суммы |
| 4 | повторять до финиша |
Типичные ошибки
- Ищут путь с меньшим числом рёбер, а не меньшей длиной.
- Пропускают обходные пути.
Что дальше
Проверьте себя на заданиях этого типа в тренажёре Upward. Начните с диагностики по предмету: она покажет, какие номера уже получаются, а какие стоит подтянуть, и по её итогам соберётся личный план подготовки.
Как это выглядит в задании 4
Пример 1 из 2
A–B = 2, B–C = 3, A–C = 7. Кратчайший путь A → C?
- Разбор
- Через B: 2 + 3 = 5 < 7.
- Ответ
- 5
Пример 2 из 2
Прямая дорога короче всегда?
- Разбор
- Нет, обход бывает короче.
- Ответ
- Не всегда
Мини-тест: 5 вопросов
- Вопрос 1 из 5
Что такое весовая матрица?
Показать ответ
Ответ: Таблица длин дорог.
Граф.
- Вопрос 2 из 5
Как искать минимум?
Показать ответ
Ответ: Сравнивать суммы.
Дейкстра.
- Вопрос 3 из 5
Пустая клетка таблицы?
Показать ответ
Ответ: Дороги нет.
Нет ребра.
- Вопрос 4 из 5
Таблица симметрична?
Показать ответ
Ответ: Для двусторонних дорог — да.
Неориентированный граф.
- Вопрос 5 из 5
Что сравнивают?
Показать ответ
Ответ: Длины, а не число рёбер.
Веса.
Проверьте всё задание 4, а не одну тему
Диагностика Upward покажет, какие задания ОГЭ по информатике стоит подтянуть в первую очередь.
Уже есть аккаунт? Войти