1956 yilda gollandlik olim Edsger Deykstra tomonidan yaratilgan algoritm bugungi kunda ham dolzarbligini yo‘qotmagan. U hatto eng murakkab sharoitlarda ham, masalan, tirbandliklar bo‘lgan yo‘l tarmoqlarida ham eng qisqa yo‘lni topishda eng yaxshi natijani ko‘rsatadi. Yaqinda olib borilgan tadqiqotlar Deykstra algoritmi har qanday ko‘cha tarmog‘ida eng qisqa yo‘lni topishda optimal ekanligini isbotladi. Bu natija 2024 yilda bo‘lib o‘tadigan Kompyuter fanlarining fundamental masalalari simpoziumida eʼlon qilinadi va u yerda eng yaxshi maqola sifatida taqdirlanadi.

Algoritmning asosiy g‘oyasi boshlang‘ich nuqtadan tarmoqning boshqa barcha nuqtalarigacha bo‘lgan vaqtning tartibli ro‘yxatini tuzishdan iborat bo‘lib, bu eng qisqa yo‘llarni tez topish imkonini beradi. Deykstra algoritmi graflar bilan ishlaydi, bunda uchburchaklar qirralar bilan bog‘langan bo‘lib, ular maʼlum bir yo‘l uchastkasini bosib o‘tish uchun ketadigan vaqt kabi vaznni bildiradi.

Hayotining oxirida Deykstra o‘z algoritmining muvaffaqiyatini qog‘oz va qalamsiz barcha tafsilotlarni ishlab chiqish orqali ortiqcha murakkabliklardan qutulishga muvaffaq bo‘lgani bilan izohlagan. U hisoblash xarajatlarini minimallashtirishga eʼtibor qaratgan va bu uning algoritmi ko‘plab boshqa tadqiqotlar uchun asos bo‘lishiga imkon bergan. Keyinchalik olimlar eng yaqin nuqtani tez topish uchun “to‘pa” deb nomlangan maxsus maʼlumotlar tuzilishidan foydalanib, uni takomillashtirishgan.

1984 yilda olimlar “to‘pa”ning takomillashtirilgan versiyasini yaratib, Deykstra algoritmining ijro vaqtining eng past chegarasiga erishishga muvaffaq bo‘lishdi va shu bilan birga eng qisqa yo‘lni topish jarayonini optimallashtirishdi. Keyingi 40 yil davomida bu algoritm bir manbadan eng qisqa yo‘l masalasi uchun eng yaxshi yechim bo‘lib qoldi.

Yaqinda olimlar algoritmning optimalligi masalasiga qaytib, universal optimal yechim yaratishga harakat qilishdi. Bu yondashuv har qanday tarmoqdagi eng yomon yo‘l tirbandlik sharoitida ham eng qisqa yo‘lni topishni nazarda tutadi. 2021 yilda olimlar guruhi baʼzi turdagi graflar uchun universal optimal algoritmlar yaratish mumkinligini isbotladi, ammo eng qisqa yo‘lni topish masalasi hal etilmagan qoldi.

2023 yilda Syurix va Kopengagen universitetlaridan bo‘lgan yosh olimlar guruhi eng yomon yo‘l ssenariylariga moslashtirish maqsadida Deykstra algoritmini qayta ko‘rib chiqdi. Ular salmoqlari manfiy bo‘lgan va murakkab tirbandlikka ega bo‘lgan tarmoqlardagi muammolarni hal qila oladigan, yanada murakkab, ammo universal optimal variantni yaratishga muvaffaq bo‘lishdi.

Universal optimal algoritmning g‘oyasi transport va logistika kabi turli sohalarda qo‘llanishi mumkin. Masalan, optimal algoritmlar jamoat transporti marshrutlarini rejalashtirishda, tirbandlikdan qochish va shaharlarda mobillikni yaxshilashda yordam berishi mumkin.

Xulosa: Deykstra algoritmi o‘tgan 70 yil ichida o‘z ahamiyatini yo‘qotmagan va hamon eng qisqa yo‘lni topishda eng yaxshi yechimlardan biri hisoblanadi. Uning universal optimal versiyasining yaratilishi esa uning qo‘llanilish doirasini yanada kengaytiradi.

Qo‘shimcha maʼlumot:

• Graf: Matematik obyekt bo‘lib, unda obyektlar (uchburchaklar) va ular o‘rtasidagi munosabatlar (qirralar) ko‘rsatilgan.
• To‘pa: Maʼlumotlar tuzilishi bo‘lib, unda elementlar ularning qiymatiga qarab tartiblangan.
• Optimal algoritm: Berilgan muammoni eng yaxshi imkoniyat bilan hal qiladigan algoritm.