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

Тема по КТП

Класс

11 класс

Предмет

Информатика

Четверть

2

Урок

№ 12

Раздел

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

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

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

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

1. 1
   Какой алгоритм обхода графа находит кратчайший путь в невзвешенном графе?

   Бинарный поиск Поиск в глубину (DFS) Поиск в ширину (BFS) Топологическая сортировка
2. 2
   Какая структура данных позволяет алгоритму Дейкстры быстро выбирать вершину с минимальным расстоянием?

   Очередь FIFO Очередь с приоритетом Связный список Стек
3. 3
   Рёбра графа: A–B = 2, A–C = 5, B–C = 1, B–D = 6, C–D = 3. Чему равна длина кратчайшего пути из A в D?

   5 6 7 8