yo’naltirilgan graflarda eng qisqa yo’lni topish algoritmlari

PPTX 22 стр. 9,1 МБ Бесплатная загрузка

22 стр.

FaylHub.uz

Скачать через Telegram

Размер 9,1 МБ

Тип файла PPTX

Страницы 22

Обновлено Дек 2025

Предварительный просмотр (5 стр.)

Прокрутите вниз 👇

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

Хотите читать дальше?

Скачайте все 22 страниц бесплатно через Telegram.

Скачать полный файл

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

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...

Этот файл содержит 22 стр. в формате PPTX (9,1 МБ). Чтобы скачать "yo’naltirilgan graflarda eng qisqa yo’lni topish algoritmlari", нажмите кнопку Telegram слева.

Теги: yo’naltirilgan graflarda eng qi… PPTX 22 стр. Бесплатная загрузка Telegram