Deykstra algoritmning so’zli tavsifi
Shunday masalalarni yechish uchun Deykstra algoritmi ancha qulay va yahshi deb topilgan.
Algoritm quyidagi qadamlardan iborat:
Dastlab, berilgan (Lex) uchidan qolgan barcha uchlargacha bir qirra uzunligidagi masofalar aniqlanadi.
Ulardan eng qisqasi “doimiy eng qisqa masofa” sifatida belgilanadi (Lex va BVa uchlari qirrasi).
Aniqlangan masofa BVa dan boshqa bor uchlargacha masofalarga qo’shiladi.
Hosil bo’lgan yig’indilar dastlab aniqlangan Lex dan qolgan uchlargacha bo’lgan masofalar bilan taqqoslanadi. Natijada masofasi qisqaroq bo’lgan uchning qirrasi tanlanadi.
Do'stlaringiz bilan baham: |