-Amaliy mashg‘ulot: Graflarda eng qisqa yo‘lni aniqlash algoritmlari va dasturlarini tuzish

Download 0,66 Mb.
bet	4/4
Sana	22.05.2024
Hajmi	0,66 Mb.
	#250518

1 2 3 4

Bog'liq
3-deadline 615-22

Amaliy qism

15-Amaliy mashg‘ulot: Graflarda eng qisqa yo‘lni aniqlash algoritmlari va dasturlarini tuzish.
Ishdan maqsad. Ushbu amaliyot ishida talabalar graflarda eng qisqa yo‘lni aniqlash algoritmlari bilan tanishib chiqishi kerak.
Qo‘yilgan masala. Talabalar topshiriq variantiga mos ravishda graflarda eng qisqa yo‘lni aniqlash algoritmlarini tuzish ko‘nikmasiga ega bo‘lishlari kerak.
Ish tartibi:

Tajriba ishi nazariy ma’lumotlarini o‘rganish;  Berilgan topshiriqning algoritmini ishlab chiqish;  Grafni tuzish va eng qisqa yo‘lni topish.
Natijalarni tekshirish;
Hisobotni tayyorlash va topshirish.

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.
Amaliy qism:

Download 0,66 Mb.

1 2 3 4

Download 0,66 Mb.