№1 · ОСНОВА АЛГОРИТМА
1. Выбор следующей вершины
Какую вершину выбирает алгоритм Дейкстры на очередном шаге?
Типы заданий
Множественный выборКраткий ответРеши задачу
Алгоритм Дейкстры
Ф.И.
Класс
Разберём, как алгоритм Дейкстры находит кратчайшие пути и почему порядок выбора вершин имеет значение. Решайте внимательно: в сложных задачах важен каждый шаг.
№2 · ИНИЦИАЛИЗАЦИЯ
2. Начальные расстояния
В начале работы алгоритма Дейкстры расстояние до стартовой вершины принимают равным какому числу?
№3 · РЕЛАКСАЦИЯ
3. Проверка нового пути
Известно: расстояние до вершины A равно 4, ребро A—B имеет вес 3, а текущее расстояние до B равно 10. Какое расстояние до B станет известным после проверки ребра A—B?
№4 · ПОШАГОВЫЙ РАСЧЁТ
4. Расстояние до вершины
Решите задачу по алгоритму Дейкстры. Неориентированный граф задан рёбрами: A—B вес 2, A—C вес 5, B—C вес 1, B—D вес 4, C—D вес 2. Стартовая вершина — A. Найдите кратчайшее расстояние от A до D.
№5 · МАРШРУТ
5. Восстановление пути
В неориентированном графе заданы рёбра: A—B вес 1, A—C вес 4, B—C вес 2, B—D вес 5, C—D вес 1, D—E вес 3. Алгоритм Дейкстры стартует из A. Запишите вершины кратчайшего пути из A в E через дефис.
№6 · РАСЧЁТ ТАБЛИЦЫ
6. Финальные расстояния
Решите задачу по алгоритму Дейкстры. Ориентированный граф задан дугами: A→B вес 3, A→C вес 8, B→C вес 2, B→D вес 7, C→D вес 1, D→E вес 4, C→E вес 9. Стартовая вершина — A. Найдите кратчайшие расстояния от A до вершин C, D и E и запишите их через пробел.
+5 заданий в этом листе
Зарегистрируйтесь — и соберите свой рабочий лист по этой теме за минуту: заданий столько, сколько нужно.
№7 · ОГРАНИЧЕНИЯ АЛГОРИТМА
7. Вес рёбер
Какое условие на веса рёбер необходимо для корректной работы алгоритма Дейкстры?
№8 · АНАЛИЗ ГРАФА
8. Недостижимая вершина
Решите задачу по алгоритму Дейкстры. Ориентированный граф задан дугами: A→B вес 2, A→C вес 6, B→C вес 1, B→D вес 5, C→D вес 2, E→D вес 1. Стартовая вершина — A. Укажите кратчайшее расстояние от A до D и объясните, почему вершина E не влияет на результат.
№9 · СРАВНЕНИЕ МАРШРУТОВ
9. Несколько равных кратчайших путей
Решите задачу по алгоритму Дейкстры. Неориентированный граф задан рёбрами: A—B вес 2, A—C вес 2, B—D вес 3, C—D вес 3, B—C вес 1, D—E вес 2, C—E вес 6. Найдите кратчайшее расстояние от A до E и перечислите все кратчайшие пути.
№10 · ВЫБОР АЛГОРИТМА
10. Дейкстра или другой алгоритм
В графе есть ребро с отрицательным весом. Какое утверждение корректно?
Создайте уникальный лист по своей теме
- Любая тема, любой уровень
- 20+ типов заданий
- 100% уникальный контент
- Со страницей ответов
- Защита от списывания
- Готово за 1 минуту
Другие темы по информатике для 11 класса
Техногенные и экономические угрозы, связанные с использованием ИКТ. Защита информации и информационная безопасностьУмная ферма как цифровое измерениеГосударственные электронные сервисы и услуги. Открытые образовательные ресурсыАнализ данных с помощью электронных таблиц; Численное решение уравнений с помощью подбора параметраПравовое обеспечение информационной безопасностиЭтапы решения задач на компьютере; Язык программирования. Основные конструкции языка; Ветвления. Составные условия; Циклы с условием. Циклы по переменнойСервисы машинного перевода и распознавания устной речи; Идентификация и поиск изображений, распознавание лиц; Самообучающиеся системы; Искусственный интеллект в компьютерных играх и обучающихПрактическое задание № 6. Корпуса ПК. Виды, характеристики, форм-факторыКонцептуальное проектирование баз данныхМодели и моделирование. Представление результатов моделированияОбработка символьных данных. Встроенные функции для обработки строкМодели и моделирование по учебнику Полякова К.Ю.
Чем удобны рабочие листы Нейрум
- По действующей программеТемы и задания совпадают со школьной программой 1–11 классов. Открыли — дали классу, без правок.
- Готово к печати, с ответамиPDF в формате A4 и ключ ответов на отдельной странице. Скачали, распечатали, раздали — без правок в Word.
- Свой лист за минутуНе нашли нужный? ИИ-конструктор соберёт лист по вашей теме, классу и типам заданий.
Вопросы и ответы
Как скачать рабочий лист «Алгоритм Дейкстры для поиска путей в графе»?
Зарегистрируйтесь бесплатно — лист сохранится в личном кабинете, откуда его можно скачать в PDF и распечатать.
Сколько заданий в листе и какие они?
В листе 10 заданий: множественный выбор, краткий ответ, реши задачу.
Соответствует ли лист ФГОС?
Да, задания ориентированы на школьную программу по информатике для 11 класса по ФГОС.
Можно ли изменить задания под свой класс?
Да. После регистрации лист открывается в конструкторе: задания можно заменить, перегенерировать или добавить новые.