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