ОГЭ · Информатика · Задание №4
Графы и кратчайший путь
Научись читать таблицу дорог, складывать длины участков и сравнивать только допустимые маршруты.Главная идея
Вершины графа обозначают точки, рёбра дороги между ними, а вес ребра показывает длину соответствующего участка.
длина маршрута = сумма весов всех его рёбер
Нет ребра значит нет прямой дороги
A → B = 4, B → C = 3
- 01Маршрут проходит через B
- 02Складываем участки: 4 + 3
- 03Длина маршрута: 7
Проверь себя перед ответом
Пустая ячейка таблицы не равна нулю. Она означает, что прямого пути между вершинами нет.
Проверь себя
От понимания к практике.
Пять выбранных задач каждого подтипа доступны без регистрации.
- 4.1 Кратчайший путь 5 бесплатно · 60 всего
- 4.2 Кратчайший путь через обязательную вершину 5 бесплатно · 60 всего
- 4.3 Самый длинный участок кратчайшего пути 5 бесплатно · 60 всего
- 4.4 Кратчайший путь без посещения вершины 5 бесплатно · 60 всего
- 4.5 Самый короткий участок кратчайшего пути 5 бесплатно · 60 всего