|
Graflarda eng qisqa yo‘lni aniqlash algoritmlari. Lug‘atlar va ularni amalga oshirish
|
| bet | 1/6 | | Sana | 15.12.2022 | | Hajmi | 1.37 Mb. | | #35030 |
Bog'liq h2WvioY3NJ3xYiG3Dvnwk3dN0xdWTzZ1BoONjuvQ 1670584835-2, jahon xojaligi va milliy iqtisodiyotda xalqaro moliyaviy iqtisodiy, Abu rayxon beruniy nomidagi toshkent davlat texnika universiteti-fayllar.org Graflarda eng qisqa yo‘lni aniqlash algoritmlari. Lug‘atlar va ularni amalga oshirish.
Graflarda eng qisqa yo‘lni aniqlash algoritmlari. Lug‘atlar va ularni amalga oshirish.
Reja:
1. 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.
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 (1-rasm).
b)
a)
1-rasm. Grafda eng qisqa masofani topish masalasi.
A) yo’naltirilmagan grafda, B) yo’naltirilgan grafda.
Masalani formal quyilishi:
G = (V, E). Yuklanishga ega bo'lgan graf berilgan. E (i, j) xar bir yoyning og'irligi berilgan – wij .
Boshlang'ich tugun s V va oxirgi tugun d V berilgan.
Ular orasidagi qisqa masofali yo'lni aniqlash talab etiladi. Yo'l uzunligi (path length, path cost, path weight) – unga kiruvchi yoylar yuklanishlari yig'indisiga teng:
(3)
2-rasm. Berilgan grafda eng qisqa masofani topish masalasining formal 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.
|
| |
