Маршрутизация и логистика

Тема по КТП

Класс

11 класс

Предмет

Информатика

Четверть

2

Урок

№ 13

Раздел

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

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

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

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

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

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

   Алгоритм Краскала Поиск в глубину Поиск в ширину Топологическая сортировка
3. 3
   Города A, B, C, D соединены дорогами: A–B 4, A–C 1, C–B 2, B–D 5, C–D 8. Найдите длину кратчайшего пути из A в D.

   7 8 9 10