yo’naltirilgan graflarda eng qisqa yo’lni topish algoritmlari

PPTX 22 pages 9.1 MB Free download

22 pages

FaylHub.uz

Download via Telegram

Size 9.1 MB

File type PPTX

Pages 22

Updated Dec 2025

Page preview (5 pages)

Scroll down 👇

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

Want to read more?

Download all 22 pages for free via Telegram.

Download full file

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

This file contains 22 pages in PPTX format (9.1 MB). To download "yo’naltirilgan graflarda eng qisqa yo’lni topish algoritmlari", click the Telegram button on the left.

Tags: yo’naltirilgan graflarda eng qi… PPTX 22 pages Free download Telegram