Настройки
Прогресс
Завершите тренировку, чтобы освоить навык.
Кратчайший путь в графе
Схема дорог между городами, у каждой из которых указана длина, — это взвешенный граф: города — вершины, дороги — ребра, длина дороги — вес ребра. Длина пути равна сумме длин его дорог. Кратчайший путь не всегда проходит через меньшее число городов и не всегда начинается с самой короткой дороги: тренажер учит сравнивать варианты и находить кратчайшие расстояния по порядку, от ближних городов к дальним.
Для кого этот тренажер
Тренажер подходит ученикам 9 класса, которые изучают графы и поиск оптимального пути на уроках информатики и готовятся к ОГЭ, где есть похожие задачи, и ученикам 11 класса для повторения темы. Нужно знать, что такое граф, вершина и ребро, и уверенно складывать однозначные числа. Способ поиска и пример разобраны в теории ниже.
Какие задания встречаются
Каждая схема составляется заново: от 6 до 8 городов, обозначенных буквами, дороги длиной от 1 до 9 соединяют соседние города и не пересекаются. Расположение городов и набор дорог меняются от задания к заданию. Кратчайший путь всегда один, в нем от трех до пяти дорог, а ближайший другой путь длиннее всего на 1–3, поэтому ответ не виден с первого взгляда. Все задания одной сложности.
Что делает ученик
Ученик прокладывает путь, отмечая города по порядку от А до последнего, и видит длину пути как сумму длин дорог. Шаг можно отменить и выбрать другую дорогу. Когда путь доходит до последнего города, он проверяется. Если путь не кратчайший, подсказка называет первый город, до которого можно добраться быстрее, и длину лучшего пути до него. В пошаговом решении для каждого города сравниваются способы до него добраться: «До В: из А 7, из Б 3 + 2 = 5, меньшее — 5».
Чему научится ученик
Ученик научится находить длину пути во взвешенном графе, сравнивать пути и находить кратчайший способом последовательного уточнения расстояний, а не угадыванием. Этот способ пригодится в задачах на маршруты и стоимость перевозок, в экзаменационных заданиях на графы и при знакомстве с алгоритмами на графах в старших классах.
Теория
Кратчайший путь во взвешенном графе
Во взвешенном графе у каждого ребра есть вес — например, длина дороги. Длина пути — сумма весов его ребер. Кратчайший путь между двумя вершинами — путь с наименьшей длиной.
Меньше ребер — не значит короче. Например, дорога из П в Т длиной 9, а из П в Р — 2 и из Р в Т — 4. Путь П–Р–Т длиной 2 + 4 = 6 короче прямой дороги, хотя в нем две дороги, а не одна.
Самая короткая первая дорога — не всегда лучший выбор. Например, из П ведут дороги в Р длиной 1 и в С длиной 3, из Р в Т — 8, из С в Т — 2. Путь через Р: 1 + 8 = 9, через С: 3 + 2 = 5. Кратчайший путь П–С–Т начинается с более длинной дороги.
Расстояния от ближних вершин к дальним. Кратчайшее расстояние от начала находят сначала для самых близких вершин, потом для следующих. Для очередной вершины сравнивают все способы прийти в нее из уже посчитанных соседей: расстояние до соседа плюс длина дороги — и берут наименьшее. Например, до Р кратчайшее расстояние 2, до С — 3, из Р в Т ведет дорога 5, из С в Т — 3. До Т: из Р 2 + 5 = 7, из С 3 + 3 = 6, меньшее — 6.
Сам путь. Путь восстанавливают от конца к началу: для конечной вершины берут соседа, через которого получилось наименьшее расстояние, для него — его лучшего соседа и так до начала. В примере выше в Т лучше всего прийти из С, а в С — прямо из начала П, значит, кратчайший путь П–С–Т длиной 6.
Частая ошибка — идти каждый раз по самой короткой дороге из текущей вершины. Такой путь может оказаться длиннее: проверяйте все способы прийти в вершину.