|
Deykstra algoritmi qanday ishlaydi?
|
| bet | 2/3 | | Sana | 07.07.2024 | | Hajmi | 1,86 Mb. | | #266910 |
Deykstra algoritmi qanday ishlaydi?
Prosedurasi
Block sxemasi
Deykstriyaning eng qisqa yo’l algoritmi
Graflar ixtiyoriy sistemaning topologiyasini ko`rish imkonini beradi. Graflar nazariyasi asosida turli nazariy va amaliy masalalarni yеchish mumkin. Amaliy masalalardan biri 2 ta tugun va tugunlar orasidagi eng qisqa yo`lni topish masalasidir. Bunda bir necha tugunlar va yoylardan iborat graf berilgan bo`ladi. Yoylarning vazni matritsa shaklida quyidagicha beriladi:
Ixtiyoriy 2 tugun orasidagi eng qisqa yo`lni topish masalasini yеchishni turli usullari mavjud. Bularga barchayo`llarni bir chekkadan qarab chiqish (prostoy), optimallashning Bellman prinsipi, va Deykstra usullarikiradi. Ulardan eng samaralisi Deykstra usulidir. Bu usulbelgilar qo`yishga bo`lgan musbatgraflarning tugunlariga vaqtinchalik asoslangandir. Bunda yoylarning vazni sonlardan iborat bo`ladi.
Masalani yеchish algoritmi.
Grafning boshlang`ich tuguniga 0 qiymat, qolganlariga esa vaqtinchalik cheksiz belgisi qo`yiladi, ya’ni:
Yuqorida bajarilgan vaqtinchalik belgilashlardan eng kichigi tanlab olinib doimiy belgi etib belgilanadi. Bu holat har bitta tugunning doimiy belgisi qo`yilguniga qadar davom ettiriladi. Bajarilayotgan har bitta qadamda albatta bitta tugun doimiy belgi oladi. Navbatdagi qadam doimiy belgi olgan tugundan davom etadi. Keyingi tugunlar to`plamini aniqlashda qaralayotgan tugundan chiqayotgan yoylar olinadi. Bunda berilgan misolda nechta tugun bo`lsa, qadamlar soni ham shuncha bo`ladi. Har qadamda har bitta holat natijasi jadvalga qayd qilib boriladi.
Formula yordamida hisoblanib olingan natijalarni solishtirishda yuqoridagi qadamlarda vaqtinchalik belgi olgan tugunlarni ham e’tiborga olish kerak bo`ladi. Jadval quyidagi tartibda tuzib olinadi: Jadvalning qatorlariga qadamlar ketma- ketligi, ustunlarga esa berilgan misoldagi barcha tugunlar nomi, oxirgi ustundan bitta oldingi ustunga doimiy belgi olgan tugun nomi, oxirgi ustunga esa belgi olgan (shu qadam uchun) tugunning kattaligi kiritiladi. Jadvaldagi ustunlar va qatorlar soni berilgan misoldagi tugunlar sonidan kelib chiqadi.
olgan tugunlar ketma-ketligi va kattaliklar Jadvalning oxirgi ikkita ustunidagi doimiy belgieng qisqa yo`l ni beradi.
Daekstra algoritmining eng qisqa yo'lini topish vazifasini hal qiling.
X0 dan x7 gacha eng qisqa yo'lni toping. Hisoblash narxi matritsaning elementlari bilan belgilanadi
|
| |
