Маршруттау және логистика есептері

КТЖ бойынша тақырып

Сынып

11-сынып

Пән

Информатика

Тоқсан

2

Сабақ

№ 13

Бөлім

Графтағы алгоритмдер (Python)

Оқу мақсаттары

• 11.2.2.1қолданбалы есептерде ең қысқа жолды табу үшін графтарды айналып өту алгоритмдерін қолдану

Сұрақтардан мысал

1. 1
   Салмақталған графта бір төбеден қалған барлық төбелерге дейінгі ең қысқа жолды табатын алгоритм қайсы?

   Дейкстра алгоритмі Прим алгоритмі Тереңдіктен іздеу (DFS) Топологиялық сұрыптау
2. 2
   Графта A–B қыры 4-ке, B–C қыры 3-ке, A–C қыры 10-ға тең. А-дан C-ға дейінгі ең қысқа жол қанша?

   3 4 7 10
3. 3
   Салмақталмаған графта ең қысқа жолды (қырлар саны бойынша) қай алгоритм табады?

   Ендіктен іздеу (BFS) Краскал алгоритмі Тереңдіктен іздеу (DFS) Флойд алгоритмі