Raqamli texnologiyalar vazirligi muhammad al xorazmiy nomidagi toshkent axborot texnologiyalari universiteti

Yo‘naltirilgan graf

Graflarda eng qisqa yo‘lni aniqlash (shortest path problem) algoritmlari va dasturlari ma’lumotlar tarmoqida eng qisqa yo‘lni topish uchun ishlatiladi. Bu algoritm va dasturlar, aloqadorliklarni tahlil qilish, tarmoqni tuzish, va boshqalar kabi turli sabablarni muvaffaqiyatli yechish uchun ishlatiladi. Quyidagi ikkita eng mashhur yo‘lni aniqlash algoritmi bilan tanishasiz:

1. Dijkstra algoritmi:
Dijkstra algoritmi grafdagi eng qisqa yo‘lni aniqlash uchun ishlatiladi. Bu algoritm aloqadorliklar va ularga bo‘lgan masofalarni hisoblash orqali eng qisqa yo‘lni topadi. Algoritm boshlanishi tug‘ilgan tug‘ilgan nuqta va qo‘ng‘iroqning saqlanishi yoki uni qiyoslash bilan boshlanadi. Algoritmi dasturiy til bilan tuzish mumkin.
2. Bellman-Ford algoritmi:
Bellman-Ford algoritmi ham grafdagi eng qisqa yo‘lni aniqlash uchun ishlatiladi. Bu algoritm negativ massivlarga (masofalarga) ega bo‘lgan graflarni ham qo‘llaydi. Bu algoritm odatda negativ massivlarga ega graflar uchun ishlatiladi.
Amaliy mashg’ulot ishlari uchun topshiriqlar.

1. 2-4 tugunlari orasidagi eng qisqs masofani toping.

2. 1-5 tugunlari orasidagi eng qisqs masofani toping.

3. A-E tugunlari orasidagi eng qisqs masofani toping.

4. A-D tugunlari orasidagi eng qisqs masofani toping.

5. 1-6 tugunlari orasidagi eng qisqs masofani toping.

6 .i- e tugunlari orasidagi eng qisqs masofani toping.

7. 1-3 tugunlari orasidagi eng qisqs masofani toping.

8. 1-5 tugunlari orasidagi eng qisqs masofani toping.

9. A-B tugunlari orasidagi eng qisqs masofani toping.

10. b-f tugunlari orasidagi eng qisqs masofani toping.

11. B-F tugunlari orasidagi eng qisqs masofani toping.

12. 1-4 tugunlari orasidagi eng qisqs masofani toping.

13. a-e tugunlari orasidagi eng qisqs masofani toping.

14. 1-4 tugunlari orasidagi eng qisqs masofani toping.

15. 1-4 tugunlari orasidagi eng qisqs masofani toping.

16. A-E tugunlari orasidagi eng qisqs masofani toping.

17. A-E tugunlari orasidagi eng qisqs masofani toping.

18. 1-4 tugunlari orasidagi eng qisqs masofani toping.

19. 0-4 tugunlari orasidagi eng qisqs masofani toping.

20. A-B tugunlari orasidagi eng qisqs masofani toping.

Nazorat savollari:
1. Dijkstra algoritmi va Bellman-Ford algoritmi orasidagi farq nima?
2. Graflar qanday turlarda aniqlanadi?
3. Graflarni tasvirlash va yaratish uchun qanday dastur tuzish mumkin?