Deykstra algoritmi (eng qisqa yo'lni topish algoritmi)

Deykstra algoritmi (eng qisqa yo'lni topish algoritmi)

• Deykstra (Dijkstra) algoritmi - gollandiyalik olim E.Deykstra (Edsger Dijkstra) tomonidan 1959 yilda ixtiro qilingan graflar algoritmi.
• Bunda Graf tepalaridan birining qolgan qismiga qadar eng qisqa masofani topadi. 
• Faqat salbiy og'irlikdagi chekkalari bo'lmagan graflar uchun ishlaydi.
• Masala: Shahar mintaqalarini birlashtiradigan magistral yo'llar tarmog'i berilgan. Ba'zi yo'llar bir tomonlama. Shahar markazidan mintaqadagi har bir shaharga eng qisqa yo'llarni toping.

• 1-chi tugundan boshqalarga qadar eng qisqa masofani topish talab qilinsin.
• Aylanalar tepaliklarni, chiziqlar ular orasidagi yo'llarni (graf qirralarini) bildiradi. Aylanalar tepaliklarning raqamlarini, qirralarning yuqorisida ularning vazni - yo'lning uzunligini ko'rsatadi.

• Boshlash
• 1 tepalikning yorlig'i 0 ga teng, qolgan tepaliklarning yorliqlari - bu erishib bo'lmaydigan son (ideal holda, cheksiz). Bu haqiqatni aks ettiradi 1 tepalikdan boshqa tepaliklargacha bo'lgan masofalar hali ma'lum emas. Grafning barcha tepalari ko'rilmagan deb belgilanadi.

• Birinchi qadam
• 1 tugunning birinchi qo'shnisi 2 tugun, chunki unga yo'l uzunligi minimaldir. Unga 1-tugunl orqali o'tadigan yo'lning uzunligi 1-tepalikka eng qisqa masofaning yig'indisiga teng (uning yorlig'i qiymati) va 1-dan 2-gacha bo'lgan chekka uzunligi, ya'ni 0 + 7 = 7. Bu 2-chi tugunlning hozirgi yorlig'idan kam (10000), shuning uchun 2-chi tugunning yangi yorlig'i 7.
• Shunga o'xshab, biz boshqa barcha qo'shnilar uchun yo'l uzunligini topamiz (3 va 6-tugunllar). 1-tugunning barcha qo'shnilari tekshiriladi. 1-cho'qqiga qadar bo'lgan minimal masofa yakuniy hisoblanadi va qayta ko'rib chiqilmaydi. Tugun 1 tashrif buyurgan deb belgilanadi.

• Ikkinchi qadam
• Algoritmning 1-bosqichi takrorlanadi. Qayta ko'rilmagan tepaliklarning "eng yaqinini" yana toping. Bu 7-yorliqli 2-tugun.
• Yana biz tanlangan tugun qo'shnilarining yorliqlarini kamaytirishga harakat qilamiz, ularga 2-tugun orqali o'tishga harakat qilamiz. 2 tepalikning qo'shnilari 1, 3 va 4 tepaliklaridir.
• Tugun 1 ga allaqachon tashrif buyurilgan. 2-tugunning keyingi qo'shnisi 3-tugundir, chunki u tepaliklarning minimal yorlig'iga tashrif buyurilmagan deb belgilangan. Agar siz unga 2 orqali kirsangiz, unda bunday yo'lning uzunligi 17 ga teng bo'ladi (7 + 10 = 17). Ammo uchinchi tepalikning amaldagi yorlig'i 9, 9 esa <17, shuning uchun yorliq o'zgarmaydi.
• 2-tugunning yana bir qo'shnisi - 4-tugun. Agar siz unga 2-chi orqali borsangiz, bunday yo'lning uzunligi 22 ga teng bo'ladi (7 + 15 = 22). 22 <10000 dan boshlab, tugun 4 yorlig'ini 22 ga qo'ying. 2 tugunning barcha qo'shnilari ko'rib chiqildi, tashrif buyurgan deb belgilang.

• Uchinchi qadam
• Biz algoritm qadamini tugun 3 ni tanlab takrorlaymiz. "Qayta ishlash" dan so'ng biz quyidagi natijalarga erishamiz.

• To'rtinchi qadam

• Beshinchi qadam

• Oltinchi qadam

• Shunday qilib, 1-tugunldan 5-tepalikka qadar eng qisqa yo'l 1 - 3 - 6 - 5 tepaliklar bo'ylab yo'l bo'ladi , chunki bu bilan masalamiz 20 ga teng minimal vaznga ega bo'lamiz.

Dijkstra algoritmi

• Eng kam tugunlar orqali o’tilgan yo’l. (vaqt ketishi - qancha)
• Tugun + yo’l + vaznli yo’l
• Dijkstra algoritmi vaznli graphlarda ‘eng arzon’ yo’lni toppish uchun ishlatiladi.
• Vaznlar yig’indisi:
• Masofa
• Narx
• Vaqt
• Vazn va boshqa
• Dijkstra algoritmi manfiy vaznli graphlar bilan ishlamaydi. Vaznlar musbat bo’lishi kerak yoki vaznsiz bo’lishi kerak.
• Dijkstra algoritmi faqat yo’naltirilgan siklik bo’lmagan (acyclic) graphlar bilan ishlaydi.

Algoritm qanday ishlaydi:

• • Boshlang’ich tugundan borish mumkin bo’lgan ‘eng arzon’ tugunni toping;
• • Eng arzon tugun qo’shnilarining ‘narxini’ toping;
• • Yuqoridagi qadamni barcha tugunlar uchun takrorlang;
• • Yakuniy yo’lni toping.

• nodes = ["Reykjavik", "Oslo", "Moscow", "London", "Rome", "Berlin", "Belgrade", "Athens"]
• init_graph = {}
• for node in nodes:
• init_graph[node] = {}
• init_graph["Reykjavik"]["Oslo"] = 5
• init_graph["Reykjavik"]["London"] = 4
• init_graph["Oslo"]["Berlin"] = 1
• init_graph["Oslo"]["Moscow"] = 3
• init_graph["Moscow"]["Belgrade"] = 5
• init_graph["Moscow"]["Athens"] = 4
• init_graph["Athens"]["Belgrade"] = 1
• init_graph["Rome"]["Berlin"] = 2
• init_graph["Rome"]["Athens"] = 2