Дошкольникам
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
ВУЗ
Для всех
Назад
Новый рекорд!

Очки опыта

0

Обракоины

0
Как вам тренажер?

Следующая тема
Очки
0
Решено
0
Время
00:00:00

Бесплатные занятия

Оформите подписку, чтобы заниматься без ограничений.

Вы не вошли в аккаунт

Создайте бесплатный аккаунт, чтобы сохранить прогресс и получить персональную подборку полезных материалов.

Настройки

Остановка

Длительность тренировки

Времени на один вопрос

Другие тренажеры по теме
Cледующая тема
Cледующая тема
Все тренажеры Все тренажеры

Ошибки

Здесь появятся ошибки, допущенные во время тренировки.

Прогресс

Завершите тренировку, чтобы освоить навык.

О тренажере

Кратчайший путь в графе

Схема дорог между городами, у каждой из которых указана длина, — это взвешенный граф: города — вершины, дороги — ребра, длина дороги — вес ребра. Длина пути равна сумме длин его дорог. Кратчайший путь не всегда проходит через меньшее число городов и не всегда начинается с самой короткой дороги: тренажер учит сравнивать варианты и находить кратчайшие расстояния по порядку, от ближних городов к дальним.

Для кого этот тренажер

Тренажер подходит ученикам 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.

Частая ошибка — идти каждый раз по самой короткой дороге из текущей вершины. Такой путь может оказаться длиннее: проверяйте все способы прийти в вершину.

Вернуться к тренажерам Вернуться к тренажерам

Предложить улучшение