Mavzu: Graf tushunchasi va uning ko’rinishlari. Graflarni tasvirlash usullari. Eng qisqa yolni to’pish algoritmi. Graf

Toʻyingan graf (dense graph) – bu qirralar soni boʻlishi mumkin boʻlgan maksimalga teng boʻlgan graf xisoblanadi.
Siyrak graf (sparse graph) – bu qirralari soni tugunlar soniga yaqin boʻlgan grafdir. (D<0.5)


Eng qisqa yolni toppish masalasi qo’yilishi
Ikkita tugun orasidag eng qisqa masofani aniqlash masalasi (single-pair shortest path problem). s tugundan d tugungacha boʻlgan eng qisqa yoʻlni aniqlash talab etiladi.
Berilgan tugundan barcha tugunlarga boʻlgan qisqa yoʻllarni aniqlash masalasi (single-source shortest path problem).
Berilgan punktga etib borishning qisqaroq yoʻlini aniqlash masalasi (single-destination shortest path problem). Grafning barcha tugunlaridan V tugunga etib borishning qisqaroq yoʻlini aniqlash talab etiladi.
Barcha oʻzaro tugunlar orasidagi qisqa masofani aniqlash masalasi (all-pairs shortest path problem). Xar bir u tugundan xar bir v tugungacha qisqaroq yoʻlni aniqlash masalasi.
Yuklanishga ega boʻlgan graf berilgan. xar bir yoyning ogʻirligi berilgan - wij
Boshlangʻich tugun sV va oxirgi tugun berilgan.
Ular orasidagi qisqaroq masofali yoʻlni aniqlash talab etiladi.
Yoʻl uzunligi (path length, path cost, path weight) – ungi kiruvchi yoylar yuklanishlari yigʻindisiga teng.



Dekstra algoritmi
Vaznga ega graflarda a punktdan b punktgacha boʻlgan eng qisqa masofani aniqlash algoritmini koʻrib chiqamiz.
graf berilgan boʻlsin. Undagi barcha yoylar manfiy boʻlmagan vaznga ega. (barcha tugunlar uchun a tugundan boshlab grafdagi boshqa tugunlargacha boʻlgan qisqa masofalarni aniqlash talab etiladi.
• Deykstra algoritmida a tugundan boshlab yoylar orqali xar bir tugungacha boʻlgan vaznlar yigʻindisi xisoblanadi va kam vaznga ega boʻlgan qiymatlar qisqa yoʻl sifatida tugunda belgilab boriladi.Algoritm barcha tugunlar koʻrib chiqilganda toʻxtatiladi.
Dastlab a tugundan boshqa tugunlargacha boʻlgan masofa vaznlarini cheksiz ∞ deb tugunda belgilab olamiz, yaʼni metka qoʻyib chiqamiz. Bu xali a tugundan koʻrilayotgan tugungacha boʻlgan qisqa masofa aniqlanmaganligini bildiradi.
a tugun metkasini 0 deb belgilaymiz.
Barcha tugunlar xali tashrif buyurilmagan deb olinadi.
Deykstra algoritmi qadamlari
Agar barcha tugunlarga tashrif buyurilgan boʻlsa algoritm yakunlanadi.
Aks xolda, xali tashrif buyurilmagan tugunlardan minimal metkali u tugun tanlanadi. u – oxirgidan bitta oldingi punkt boʻladigan barcha marshrutlar koʻrib chiqiladi. U tugunga qoʻshni boʻlgan tugunlarning yoy vazni va metkalari yigʻindisi xisoblanadi va u agar qoʻshni tugun metkasidan kichik boʻlsa, metkadagi qiymat bilan almashtiriladi.
Barcha qoʻshni tugunlar koʻrib chiqilgach, u tugun tashrif buyurilgan deb belgilanadi.