Ең қысқа жолды іздеу

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

Сынып

11-сынып

Пән

Информатика

Тоқсан

2

Сабақ

№ 12

Бөлім

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

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

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

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

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

   Дейкстра алгоритмі екілік іздеу көпіршікпен сұрыптау тереңдікпен жүру (DFS)
2. 2
   Салмақсыз графта ең қысқа жолды қырлар саны бойынша табу үшін қандай әдіс тиімді?

   Прим алгоритмі екілік іздеу енінен жүру (BFS) тереңдікпен жүру (DFS)
3. 3
   Дейкстра алгоритмі қандай жағдайда дұрыс емес нәтиже беруі мүмкін?

   граф байланыспаған болса графта цикл болса төбелер саны мыңнан асса қырлардың салмағы теріс болса