Internet va axborot kommunikatsiyasi fakulteti

Dijkstra algoritmi
Qadam 1. Birinchisidan tashqari barcha cho'qqilarga cheksizlikka teng og'irlik, birinchi cho'qqiga esa 0 ga teng bo'ladi.
Qadam 2. Barcha uchlari tanlanmagan.
Qadam 3. Birinchi tepalik oqim deb e'lon qilinadi.
4-qadam. Barcha tanlanmagan cho'qqilarning og'irligi formula bo'yicha qayta hisoblab chiqiladi: tanlanmagan cho'qqining og'irligi - bu cho'qqining eski og'irligidan minimal son, joriy cho'qqi og'irligi yig'indisi va chekka og'irligi. joriy cho'qqini tanlanmagan bilan bog'lash.
Qadam 5. Tanlanmagan cho'qqilar orasidan minimal og'irlikdagi cho'qqi qidiriladi. Agar bittasi topilmasa, ya'ni barcha cho'qqilarning og'irligi cheksizlikka teng bo'lsa, unda marshrut mavjud emas. Demak, chiqish yo'li. Aks holda, topilgan cho'qqi joriy bo'ladi. U ajralib turadi.
Qadam 6. Agar joriy cho'qqi oxirgi bo'lsa, unda yo'l topiladi va uning og'irligi oxirgi cho'qqining og'irligidir.
7-qadam. 4-bosqichga o'ting.
Dasturiy ta'minotni amalga oshirishda Dijkstra algoritmi boshlang'ich cho'qqidan eng qisqa yo'llar allaqachon ma'lum bo'lgan S cho'qqilar to'plamini tuzamiz. Har bir qadamda qolgan cho'qqilardan biri S to'plamga qo'shiladi, boshlang'ich cho'qqigacha bo'lgan masofa qolgan cho'qqilarga qaraganda kamroq. Bunda D massividan foydalanamiz, unda uzunliklar yoziladi eng qisqa yo'llar har bir tepalik uchun. Agar S to'plamda grafikning barcha uchlari bo'lsa, D massivida uzunliklar bo'ladi eng qisqa yo'llar boshlang'ich cho'qqidan har bir cho'qqigacha.
Yuqoridagi massivlarga qo'shimcha ravishda C uzunlikdagi matritsadan foydalanamiz, bu erda C elementi chetning uzunligi (i, j), agar chekka bo'lmasa, uning uzunligi cheksizlikka teng deb qabul qilinadi, bu qirralarning har qanday haqiqiy uzunligidan kattaroqdir. Aslida, C matritsasi qo'shnilik matritsasi, unda barcha nol elementlar cheksizlik bilan almashtiriladi.
Dijkstra algoritmi qanday ishlaydi. Dijkstra algoritmi
Deykstra algoritmidan foydalanib eng qisqa yo'lni topish masalasini yeching.
X0 dan X7 gacha bo'lgan eng qisqa yo'lni toping. Grafik xarajatlar matritsasi elementlari bilan berilgan
Keling, ushbu grafikni tuzamiz

X0 elementidan boshlaylik va unga 0 belgisini belgilaymiz, chunki uning barcha qo'shnilarini ko'rib chiqing hali hech qanday belgilar yo'q, keyin biz ularga tegishli uzunliklarni tayinlaymiz:

Barcha qo'shnilar X0 hisobga olinadi, biz uni belgilaymiz va X1 tepasiga o'tamiz. Uning qo'shnilari X0, X2, X4, lekin X0 belgilangan, biz buni hisobga olmaymiz. X2
uchun:  , yorliqni qoldiring.
X4 uchun:  , yorliqni almashtiring. X1 vertexning barcha qo'shnilari hisobga olinadi, biz uni belgilaymiz

yuqori X2 ga o'ting. Uning qo'shnilari X0, X1, X3, X4, X5, X6, lekin X0, X1 belgilangan, biz ularni hisobga olmaymiz.
X3 uchun:  , yorliqni qoldiring.
X5 uchun:  , yorliqni almashtiring.
X4 uchun:  , yorliqni qoldiring.
X6 uchun:  , yorliqni almashtiring.
X2 vertexining barcha qo'shnilari ko'rib chiqildi, biz uni belgilaymiz.

yuqori X3 ga o'ting. Uning qo'shnilari X0, X2, X6, lekin X0, X2 belgilangan, biz ularni hisobga olmaymiz.
X6 uchun:  , yorliqni qoldiring.
X3 vertexining barcha qo'shnilari ko'rib chiqildi, biz uni belgilaymiz.

yuqori X4 ga o'ting. Uning qo'shnilari X1, X2, X5, X7, lekin X1, X2 belgilangan, biz ularni hisobga olmaymiz.
X5 uchun:  , yorliqni almashtiring.
X7 uchun:  , yorliqni almashtiring.
X4 vertexining barcha qo'shnilari ko'rib chiqildi, biz uni belgilaymiz.

yuqori X5 ga o'ting. Uning qo'shnilari X2, X4, X6, X7, lekin X2, X4 belgilangan, biz ularni hisobga olmaymiz.
X6 uchun:  , yorliqni qoldiring.
X7 uchun:  , yorliqni qoldiring.
X5 vertexining barcha qo'shnilari ko'rib chiqildi, biz uni belgilaymiz.



yuqori X6 ga o'ting. Uning qo'shnilari X2, X3, X5, X7, lekin X2, X3, X5 belgilangan, biz ularni hisobga olmaymiz.
X7 uchun:  , yorliqni qoldiring.
X6 vertexining barcha qo'shnilari ko'rib chiqildi, biz uni belgilaymiz. Va qolgan X7 ni belgilaymiz, barcha tepaliklar hisobga olinadi.

Xulosa: X0 dan X7 gacha bo'lgan eng qisqa yo'lning uzunligi 101 ga teng, bu yo'l: X7-X4-X1-X0.
Eng qisqa yo'lni topish misolini ko'rib chiqing. Shahar hududlarini bog'laydigan avtomobil yo'llari tarmog'i berilgan. Ba'zi yo'llar bir tomonlama. Shahar markazidan mintaqadagi har bir shaharga eng qisqa yo'llarni toping.
Ushbu muammoni hal qilish uchun siz foydalanishingiz mumkin Dijkstra algoritmi- 1959 yilda golland olimi E. Deykstroy tomonidan ixtiro qilingan grafiklar bo'yicha algoritm. Grafikning bir cho'qqisidan qolgan barcha nuqtalarigacha bo'lgan eng qisqa masofani topadi. Faqat manfiy og'irlikdagi qirralari bo'lmagan grafiklar uchun ishlaydi.
1-cho'qqidan qolgan barcha nuqtalargacha bo'lgan eng qisqa masofalarni topish talab qilinsin.
Doiralar cho'qqilarni, chiziqlar ular orasidagi yo'llarni (grafikning qirralarini) ko'rsatadi. Doiralar cho'qqilarning raqamlarini ko'rsatadi, qirralarning tepasida ularning og'irligi - yo'lning uzunligi ko'rsatilgan. Har bir cho'qqi yonida qizil yorliq mavjud - bu cho'qqiga 1-cho'qqigacha bo'lgan eng qisqa yo'lning uzunligi.
1 cho'qqisining yorlig'i o'zi 0 ga teng, qolgan cho'qqilarning teglari etib bo'lmaydigan raqam (ideal, cheksizlik). Bu 1-cho'qqidan boshqa cho'qqilargacha bo'lgan masofalar hali ma'lum emasligini aks ettiradi. Grafikning barcha cho'qqilari ko'rilmagan deb belgilangan.