yo’naltirilgan graflarda eng qisqa yo’lni topish algoritmlari

PPTX 22 sahifa 9,1 MB Bepul yuklash

22 sahifa

FaylHub.uz

Telegram orqali yuklab olish

Hajm 9,1 MB

Fayl turi PPTX

Sahifalar 22

Yangilangan Dek 2025

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇

1 / 22

yo’naltirilgan graflarda eng qisqa yo’lni topish algoritmlari yo’naltirilgan graflarda eng qisqa yo’lni topish algoritmlari reja: 1. deykstra algoritmi 2. bellman-ford algoritmi 3. johnson algoritmi 4. floyd-warshall algoritmi eng qisqa yo’lni topish masalasi graflarda eng qisqa yo’lni topish masalasi ikki xil tarzda qo’yilishi mumkin: 1. bir tugundan boshqa tugunlargacha bo’lgan eng qisqa masofani topish 2. barcha tugunlardan boshqa tugunlargacha bo’lgan eng qisqa masofalarni topish (all pairs shortest paths apsp) birinchi turdagi masalani yechishdagi eng mashhur algoritmlar: deykstra va bellman-ford algoritmlari. ikkinchi turdagi masalani yechishdagi eng mashhur algoritmlar: johnson va floyd-warshall algoritmlari. asosiy belgilashlar: g(v, e, w) graf berilgan bo’lsin. v – tugunlar to’plami (|v| - tugunlar soni); e – yoylar to’plami (|e| - yoylar soni); w – vaznlar to’plami; (u, v) – u tugundan v tugunga boruvchi yoy; - i tugundan j tugunga boruvchi yoy vazni; d(v) – u tugundan v tugungacha bo’lgan yo’l uzunligi deykstr algoritmi deykstr algoritmi manfiy vaznga …

2 / 22

p massiv eng qisqa yo’l marshrutini saqlaydi. qadamlar metka yo'l uzunliklari tugun nomlari → 1 2 3 4 5 6 0 d 0 ∞ ∞ ∞ ∞ ∞ p 1 d p 2 d p 3 d p 4 d p 5 d p 6 d p 1 0 9 ∞ ∞ ∞ 2 0 9 ∞ 6 9 1 5 1 5 0 9 22 6 2 9 1 4 5 5 1 0 9 10 6 2 9 1 2 5 1 5 0 9 10 6 2 9 1 2 5 1 5 1 2 0 9 10 6 2 9 1 2 5 1 5 deykstr algoritmini suvning tarqalishiga o’xshatishadi deykstr algoritmi ishlash tezligi: qo’shnilik matritsasi bilan ishlaganda o() qo’shnilik ro’yhati bilan ishlaganda o(|e|*) deykstr algoritmining asosiy kamchiligi manfiy vaznga ega graflarda ishlay olmaydi!!! bellman-ford algoritmi bellman-ford algoritmi ham bir tugundan boshqa barcha tugunlagacha bo’lgan eng …

3 / 22

-7 d[v] = min(d[v], d[u] + w[u,v]) p[v] = u 3-4 uchun ∞ > 2 - 7 d[3] = -5 p[2] = 3 4 → 2 qirrani qaraymiz d[u] = d[4] = -5 d[v] = d[2] = 5 w[u, v] = w[1, 2] = 11 d[v] = min(d[v], d[u] + w[u,v]) p[v] = u 4-2 uchun 5 4 ham 4 -> 1 ham bir xil bo’ladi. 3. p(0) jadvaldagi bo’sh elementlar p[i, j] = j tarzda to’ldiriladi. 4. keyingi qadamga o’tiladi. 1 2 3 4 5 1 0 1 ∞ 1 5 2 9 0 3 2 ∞ 3 ∞ ∞ 0 4 ∞ 4 ∞ ∞ 2 0 3 5 3 ∞ ∞ ∞ 0 1 2 3 4 5 1 - 2 3 4 5 2 1 - 3 4 5 3 1 2 - 4 5 4 1 2 3 - 5 5 1 2 3 4 …

4 / 22

a ega sikl bilan ishlay olmaydi. floyd-warshall algoritmi xossalari e’tiboringiz uchun rahmat! multimedia dasturlarini ham o’rganib qo’ying!  image1.png image1.jpg image2.gif image2.png image3.gif image4.gif image4.png image5.png image6.png image7.png image8.png image9.png media1.mp4 image10.png image11.png image110.png image12.png image21.png image22.png image23.png image24.png image25.png image26.png image13.png image14.png image15.png image16.png image17.png image18.png image19.png image20.png image27.png image28.png image29.png /docprops/thumbnail.jpeg

5 / 22

yo’naltirilgan graflarda eng qisqa yo’lni topish algoritmlari - Page 5

Ko'proq o'qimoqchimisiz?

Barcha 22 sahifani Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"yo’naltirilgan graflarda eng qisqa yo’lni topish algoritmlari" haqida

yo’naltirilgan graflarda eng qisqa yo’lni topish algoritmlari yo’naltirilgan graflarda eng qisqa yo’lni topish algoritmlari reja: 1. deykstra algoritmi 2. bellman-ford algoritmi 3. johnson algoritmi 4. floyd-warshall algoritmi eng qisqa yo’lni topish masalasi graflarda eng qisqa yo’lni topish masalasi ikki xil tarzda qo’yilishi mumkin: 1. bir tugundan boshqa tugunlargacha bo’lgan eng qisqa masofani topish 2. barcha tugunlardan boshqa tugunlargacha bo’lgan eng qisqa masofalarni topish (all pairs shortest paths apsp) birinchi turdagi masalani yechishdagi eng mashhur algoritmlar: deykstra va bellman-ford algoritmlari. ikkinchi turdagi masalani yechishdagi eng mashhur algoritmlar: johnson va floyd-warshall algoritmlari. asosiy belgilashlar: g(v, e, w) graf berilgan bo’lsin. v – tugunlar to’pla...

Bu fayl PPTX formatida 22 sahifadan iborat (9,1 MB). "yo’naltirilgan graflarda eng qisqa yo’lni topish algoritmlari"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: yo’naltirilgan graflarda eng qi… PPTX 22 sahifa Bepul yuklash Telegram