Поиск кратчайшего пути

Тема по КТП

Класс

11 класс

Предмет

Информатика

Четверть

2

Урок

№ 22

Раздел

Алгоритмы на графах (Python)

Цели обучения

• 11.2.2.1использовать алгоритмы обхода графов для нахождения кратчайшего пути в прикладных задачах

Примеры вопросов

1. 1
   Какой алгоритм находит кратчайшие пути во взвешенном графе, каждый раз выбирая непосещённую вершину с наименьшим текущим расстоянием?

   Алгоритм Дейкстры Алгоритм Прима Поиск в глубину Поиск в ширину
2. 2
   Какой алгоритм найдёт кратчайший путь по числу рёбер в невзвешенном графе?

   Алгоритм Дейкстры Алгоритм Краскала Поиск в глубину Поиск в ширину
3. 3
   Какая структура данных обеспечивает порядок обхода вершин в поиске в ширину?

   Куча Очередь Словарь Стек