ОГЭ: Кратчайший путь в графе
Информатика, 9 класс · ОГЭ: Графы и пути
📚 Программа 9 класса · модуль «Практика: ОГЭ: Графы и пути» — тренажёр 1 из 1. За освоение тренажёра — +15 ★.
Загрузка…
Правило и как решать
Идём по вершинам по порядку, считая минимальные длины.
Подсказка: Разбери условие по шагам и посчитай.
Примеры с разбором
Пример 1
Дороги заданы списком (в скобках указана длина): А→Б(2), А→В(6), А→Е(2), Б→Г(3), Б→Е(6), В→Е(1), Г→Д(2), Д→Е(7). Найди длину кратчайшего пути из А в Е.
Ответ: 2
Решение: Находи кратчайшие пути к городам по порядку.
Пример 2
Дороги заданы списком (в скобках указана длина): А→Б(7), А→В(5), А→Г(8), А→Е(4), Б→В(3), Б→Г(9), В→Г(5), В→Е(7), Г→Д(8), Д→Е(5). Найди длину кратчайшего пути из А в Е.
Ответ: 4
Решение: Находи кратчайшие пути к городам по порядку.
Пример 3
Дороги заданы списком (в скобках указана длина): А→Б(4), А→Г(1), Б→Г(2), Б→Д(4), Б→Е(3), В→Д(4), В→Е(1), Г→Д(2), Д→Е(4). Найди длину кратчайшего пути из А в Е.
Ответ: 7
Решение: Находи кратчайшие пути к городам по порядку.
Другие тренажёры: Информатика, 9 класс
💻Сколько вопросов «да/нет» нужно, чтобы угадать числоИнформатика · Множества💻Нарисуй картинку по шестнадцатеричному кодуИнформатика · Кодирование💻Сортировка пузырьком по шагамИнформатика · Алгоритмы💻ОГЭ: Объём изображенияИнформатика · ОГЭ: расчёты по информатике💻ОГЭ: Время передачи файлаИнформатика · ОГЭ: расчёты по информатике💻ОГЭ: Длина двоичного кода символаИнформатика · ОГЭ: расчёты по информатике