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