Graflarda eng qisqa yo‘lni aniqlash algoritmlari Breadth first search bfs eniga qarab qidirish algortimi

O’ZBEKISTON RESPUBLIKASI O’LIY TA’LIM , FAN VA INNOVATSIYALAR VAZIRLIGI

• O’ZBEKISTON RESPUBLIKASI O’LIY TA’LIM , FAN VA INNOVATSIYALAR VAZIRLIGI
• MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALAR UNIVERSITETI

Ma’lumotlar tuzilmasi va algoritmlar
Mustaqil ish
Guruhi: SWD009
Bajardi : Zokirov Bakirali
Tekshirdi : Raxmanov Askar Tajibayevich

Graflarda eng qisqa yo‘lni aniqlash algoritmlari

Graflarda eng qisqa yo‘lni aniqlash algoritmlari.

• Reja:
• 1.Graflarda eng qisqa yo’lni aniqlash haqida
• 2.Graflarda eng qisqa yo’lni aniqlash algoritmlar tahlili
• 2.1. Floyd – Uorshell algoritmi
• 2.2. Ford – Belmann algoritmi
• 2.3. Deykstra algoritmi

Graflarda eng qisqa yo’lni aniqlash haqida Graflar nazariysida eng qisqa yo’lni aniqlash muhim klassik masalalaridan biri deb hisoblanadi. Uni hisoblash va echimlarni topish uchun bir qancha algoritmlari mavjud.

Eng qisqa yo’l masalasi (inglizchada – shortest path problem) – bu grafning ikkita tugun orasidagi eng qichik yo’l (masofa, zanjir, marshrut) topish masalasidir, qaysidaki yoylarning vaznilarining yig’indisi minimal qiymatga ega. Qisqa (oddiy) zanjir geodezik zanjir ham aytiladi.

Data structures and algorithm

• Eng qisqa yo’l masalasi (inglizchada – shortest path problem) – bu grafning ikkita tugun orasidagi eng qichik yo’l (masofa, zanjir, marshrut) topish masalasidir, qaysidaki yoylarning vaznilarining yig’indisi minimal qiymatga ega. Qisqa (oddiy) zanjir geodezik zanjir ham aytiladi.
• Ushbu masalani adabiyotlarda bir nechta boshqa nomlanishi ham uchratish mumkin: minimal masofa masalasi, dilijans masalasi, qisqa masofa masalasi va boshqalar.

Grafda eng qisqa masofani topish masalasi yo’naltirilgan, yo’naltirilmagan va aralash graflarda echimini aniqlash mumkin

. Grafda eng qisqa masofani topish masalasi
yo’naltirilmagan grafda
yo’naltirilgan grafda