TARMOQDA ENG QISQA MASOFANI TOPISH MASALASI (DYEKSTR ALGORITMI)

Dijkstra algoritmi • Dijkstra algoritmi berilgan cho'qqidan qolgan barcha nuqtalarga minimal yo'lni topish algoritmidir. • Ushbu algoritm og'irlikdagi yo'naltirilmagan grafik misolida ko'rsatiladi.

Grafik misol

Algoritm tahlili Dastlab, grafikning barcha cho'qqilari asl cho'qqigacha bo'lgan masofani tavsiflovchi biron bir belgini oladi. Bu masofa ma'lum emas, shuning uchun biz masofa hali ham juda katta raqam deb taxmin qilamiz. Yo'l boshlanadigan cho'qqi nol bilan belgilanadi. Qayta ishlangan uchlarini ham belgilaymiz.

Algoritm tahlili. • Algoritm qayta ishlangan cho'qqining qo'shnilarini chetlab o'tadi. • Qo'shnilarning har biriga masofa ishlov beriladigan yorliqning yig'indisi va chekkaning qo'shnisiga og'irligi sifatida hisoblanadi. Qabul qilingan qiymat qo'shni cho'qqining yorlig'i bilan taqqoslanadi va agar olingan qiymat kamroq bo'lsa, u holda bu qiymat qo'shni cho'qqiga tayinlanadi. • Qo'shnilardan o'tgandan so'ng, qayta ishlangan tepalik qayta ishlangan deb belgilanadi. • Yangi qayta ishlangan cho'qqi allaqachon qayta ishlanganiga eng yaqin bo'lganidek qidiriladi. Bunday holda, yangi qayta ishlangan cho'qqi ishlov berilmasligi kerak. • O'tish barcha uchlari qayta ishlanmaguncha davom etadi.