Referat. Fan: Ma’lumotlar tuzilmasi va algoritmi. " Kif" gurux: 203 talaba: xushvaqtov a

Deykstr algoritmi.Dijkstraning algoritmi - bu Gollandiyalik olim Edsger Diykstra 1959 yilda ixtiro qilgan grafik algoritm. Grafikning uchidan boshqalarigacha bo'lgan eng qisqa yo'llarni topadi. Algoritm faqat salbiy og'irliksiz chizmalar uchun ishlaydi. Algoritm dasturlash va texnologiyalarda keng qo'llaniladi, masalan, OSPF va IS-IS marshrutlash protokollari undan foydalanadi.

Aytaylik, biz birinchi cho'qqidan qolgan barcha masofalarga eng qisqa masofani topmoqchimiz.

Doira uchlarini, chiziqlar esa ularning orasidagi yo'llarni (grafik qirralarini) ko'rsatadi. Doira uchlari sonlarini, qovurg'alarining ustiga ularning og'irligi - yo'l uzunligini bildiradi. Yorliq har bir verteks yonida qizil rang bilan belgilanadi - bu vertexdan 1 verteksgacha bo'lgan eng qisqa yo'l uzunligi.

Birinchi qadam. Bizning misolimiz uchun Dijkstra algoritmini ko'rib chiqing. Minimal yorliq 1 vertexga ega. Uning qo'shnilari 2, 3 va 6 cho'qqilari.

1-vertexning birinchi qo'shnisi 2-vertexdir, chunki unga borish yo'li minimaldir. 1 vertex orqali o'tadigan yo'lning uzunligi 1 vertex yorlig'i qiymatining yig'indisiga va 1-dan 2-ga o'tuvchi qirralarning uzunligiga teng, ya'ni 0 + 7 = 7, bu 2-sonli vertexning hozirgi yorlig'idan kam, shuning uchun yangi yorliq 2-chi. vertex 7 ga teng.

Biz shunga o'xshash operatsiyani 1-verteksning boshqa ikkita qo'shnisi bilan - 3 va 6-chi bilan bajaramiz

1-vertexning barcha qo'shnilari tekshirilgan. Hozirgi eng yuqori cho'qqiga 1 masofa yakuniy hisoblanadi va qayta ko'rib chiqilmaydi (birinchi navbatda E. Dijkstra bu shunday ekanligini isbotladi). Ushbu cho'qqiga tashrif buyurganligini ta'kidlash uchun uni grafikadan kesib olamiz.

Ikkinchi qadam. Algoritm bosqichi takrorlanadi. Yana biz kutilmagan cho'qqilarning "eng yaqinini" topamiz. Bu 7-yorliqli 2-vertex.

Yana, biz tanlangan vertexning qo'shnilarining yorliqlarini qisqartirishga harakat qilamiz, ular orqali 2-chi vertex orqali o'tishga harakat qilamiz. 2 cho'qqilarining qo'shnilari 1, 3 va 4 cho'qqilari.

2-sonning birinchi (qo'shni) qo'shnisi 1-vertex. Ammo u allaqachon tashrif buyurgan, shuning uchun biz 1-verteks bilan hech narsa qilmaymiz.

2-vertexning keyingi qo'shnisi 3-vertexdir, chunki u uchiga minimal tashrif buyurilgan deb belgilangan. Agar siz unga 2 ga kirsangiz, u holda bu yo'lning uzunligi 17 ga teng bo'ladi (7 + 10 = 17). Ammo uchinchi uchining hozirgi yorlig'i 9 ga teng, bu 17 dan kam, shuning uchun yorliq o'zgarmaydi.

2-sonli vertexning yana bir qo'shnisi - 4-sonli vertex . 22 <{\ displaystyle \ infty} \ intyy bo'lgani uchun 4 dan 22 gacha vertex yorlig'ini o'rnating.

2-vertexning barcha qo'shnilari skanerdan o'tkaziladi, unga masofani muzlatib qo'ying va tashrif buyurgan deb belgilang.

Uchinchi qadam. Algoritm bosqichini 3-sonli verteksni tanlab takrorlaymiz. "Qayta ishlash" dan so'ng quyidagi natijalarga erishamiz:

Keyingi qadamlar. Qolgan uchlari uchun algoritm bosqichini takrorlaymiz. Bu mos ravishda 6, 4 va 5-sonli vertikallar bo'ladi.