Кратчайший путь (ОГЭ)
30.03.2022
Необходимо по определенном условию найти кратчайший путь из одной точки в другую. При этом данные представлены в таблице с указанием длины пути. Решение задач на определение кратчайшего пути — это задание № 4 в ОГЭ.
Это задание можно решить двумя способами:
- При помощи алгоритма Дейкстры
- При помощи построения графа по таблице расстояний.
Для ОГЭ удобнее второй способ, т.к. в заданиях ОГЭ этот способ быстрее и удобнее.
Задача 1 Определить кратчайший путь
Мы видим, что на пересечении двух населенных пунктов, например, А и B есть какая-то цифра, то это значит, что есть дорога на данном участке и ее протяженность 3 км (в нашей задаче).
Все, что осталось сделать – это построить граф, чтобы визуально найти самую короткую дорогу.
Графы составляйте как можно просторнее, чтобы самим не запутаться.
На рисунке мы видим сразу, что из А в F есть прямая дорога = 15 км
АВDF = 3+4+6 = 13
Но если мы будем так искать руками, то это будет чуть подольше.
Давайте определимся с вами с ключевыми точками. Точка D – ключевая точка через которую мы идем по дороге от А в F.
Теперь нужно посмотреть, а как же попасть в точку D быстрее?
Это может быть через пункт В 3+4 = 7 км
Или через пункт С 5+2 = 7 км.
Такой пример попался, что расстояние двух дорог одинаково.
Далее из D в F можем попасть напрямую DF = 6 км, а можем через Е 3+4 = 7 км
Соответственно, единственно короткая дорога в данной задаче будет:
АВDF 3 км + 4 км + 6 км = 13 км
Ответ: 13
Основное состоит в том, что когда построили граф, то необходимо ориентироваться на точки, которые встречаются на пути. В этой задача определяем ключевую точку D, т.к. через нее проходит больше всего дорог при переходе от А до F. И определяем наиболее короткую дорогу до ключевой точки сначала, а потом от ключевой точки до конечной.
Задача 2. Определить кратчайший путь
Рассмотрим задание 2
По условию нам необходимо найти кратчайший путь между пунктами В и D, но граф нам также нужно строить.
На графе видно, что один прямой путь у нас уже есть из D в E равный 4. Эта дорога из Е единственная.
Далее мы идем из В и видим, что можно пройти через А, а можем пройти и через С.
Если проходим через А, то будет 1 + 4 = 5
Если проходим через А и С, то будет 1+2+1 = 4
Третья дорога ВСЕ = 4+1 = 5
Следовательно, самый короткий путь будет:
ВАСЕD= 1+2+1+4=8 км
Ответ: 8
Следующее задание выглядит необычно, т.к. присутствуют непривычные нам переменные. Здесь у нас названия населенных пунктов.
Задание 3. Определить кратчайший путь
В результате задача стоит следующим образом: нужно пройти из Вершков в Ивановское.
Проще всего это задание сделать, если присвоить названиям поселка те же английские буквы для того, чтобы не запутаться.
Можно поставить и русские буквы по первым буквам названий, но тут могут быть совпадения, например, в нашем задании два поселка с названием с буквы Д.
Поэтому просто ставим английские буквы по алфавиту.
Далее строим граф
Еще раз замечаем, что мы ищем короткий путь из деревни Вершки (В) в поселок Ивановский (F).
Что видим?
Прямой путь сразу видно через пункт D 4+5=9
Теперь проверяем другие пути, вдруг будет короче.
Идти через А и С нет смысла, т.к. АС = 8 км.
Можем пойти из В в Е 2 км, далее в пункт С и в пункт F.
ВЕС = 2+1+3 = 6 км
Ответ: 6
Граф не такой точный метод решения, но он очень простой для понимания: можно визуально нарисовать граф и отследить все дороги.
Да, может понадобиться время для тренировки, чтобы научиться быстро определять. Но даже если решать это задание, ведя по графу пальцем, время на решение уйдет всего 2-3 минуты и несколько минут на оформление графа.
Задание 4. Определение кратчайшего пути
В этом задании мы также должны найти кратчайший путь, но есть ограничение – надо обязательно пройти через пункт С.
Задание становится проще, т.к. мы понимаем, как будет строиться наш путь.
Строим граф:
Причем путь из А в Е можно не строить, так как эта дорога прямая и через пункт С не проходит, т.е. не выполняется условие.
Граф получился у нас менее нагружен. Нарисовали пути, подписали. Обязательно выберите время и проверьте еще раз правильность графа по таблице, чтобы ничего не упустить.
Граф построен. Мы должны пройти из пункта А через точку С в пункт Е.
В пункт С можно попасть либо через пункт В 1+2 = 3; либо из А в С – это 4 км. Через D пройти не сможем, т.к. один пункт посещать два раза нельзя, а в этом случае будет именно этот вариант.
Соответственно, самой короткой дорогой будет дорога через В: АВС 1+2 = 3
Затем из С можно попасть только в D, а затем в Е:
ADCDE = 1+2+3+2 = 8 км
Ответ 8 км.
Примеры решения задач по информационным моделям (подготовка к ЕГЭ) по ссылке.
Экономист по первому образованию и учитель информатики по второму. Преподаю в школе информатику, программирование, сайтостроение, экономику.
Задание 1 имеет несколько типов. На допах мы рассматриваем все последовательно.