Axborotlashtirish texnologiyalari

Deykstra algoritmning so’zli tavsifi

Shunday masalalarni yechish uchun Deykstra algoritmi ancha qulay va yahshi deb topilgan.

Algoritm quyidagi qadamlardan iborat:

1. 
   Dastlab, berilgan (Lex) uchidan qolgan barcha uchlargacha bir qirra uzunligidagi masofalar aniqlanadi.
   
2. 
   Ulardan eng qisqasi “doimiy eng qisqa masofa” sifatida belgilanadi (Lex va BVa uchlari qirrasi).
   
3. 
   Aniqlangan masofa BVa dan boshqa bor uchlargacha masofalarga qo’shiladi.
   
4. 
   Hosil bo’lgan yig’indilar dastlab aniqlangan Lex dan qolgan uchlargacha bo’lgan masofalar bilan taqqoslanadi. Natijada masofasi qisqaroq bo’lgan uchning qirrasi tanlanadi.
   
5. 
   BVa uchi, eng qisqa masofa aniqlangan uch sifatida, ruyhatdan o’chiriladi. Ruyhatga boshqa uch qo’yiladi, masalan, Roa. Bva o’z navbatida, boshqa, izlanayotgan ruyhatga qo’yiladi.
   

Keyingi eng qisqa masofani topish uchun butun jarayon qayta bajariladi. BVa dan keyin yana bir uch ruyhatga qo’yiladi. Dastlabkisi esa ruyhatdan o’chiriladi. Sikl Bed va Lex uchlarini bog’lash uchun belgilangan qirralar aniqlanishi bilan to’xtatiladi.

Ko’rilgan misolda Bed uchi Lex dan boshlab eng oxirgi bo’lib chiqdi, ya’ni Lex dan Bed gacha eng qisqa masofani topish uchun biz Lex dan barcha qolgan uchlargacha eng qisqa yo’llarni topishga majbur bo’ldik.

Demak, eng yomon holatda 2 ta berilgan uchlar orasidagi eng qisqa yo’lni topish, bir berilgan nuqtadan qolgan barcha nuqtalargacha eng qisqa yo’l topish masalasi bilan murakkabligi bir xil bo’ladi.