Graflarda eng qisqa yo'lni aniqlashning deykstra algoritmlari guruh: swd025 bajardi: yaxshiliqov sh tekshirdi: ganixodjaeva d

GRAFLARDA ENG QISQA YO'LNI ANIQLASHNING DEYKSTRA ALGORITMLARI

GURUH: SWD025

BAJARDI: YAXSHILIQOV SH

TEKSHIRDI: GANIXODJAEVA D

MUSTAQIL ISH
TATU
TOSHKENT2022
MA’LUMOTLAR TUZILMASI VA ALGORITMLAR

REJA:

Graflarda eng qisqa yo’lni aniqlash haqida
Graflarda eng qisqa yo’lni aniqlash algoritmlar tahlili
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. 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
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.
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. Berilgan tugundan barcha tugunlarga bo’lgan qisqa yo’llarni aniqlash masalasi (single-source shortest path problem). Berilgan punktga yetib borishning qisqaroq yo’lini aniqlash masalasi (single-destination shortest path problem). Grafning barcha tugunlaridan V tugunga yetib borishning qisqaroq yo’lini aniqlash talab etiladi. Barcha o’zaro tugunlar orasidagi qisqa masofani aniqlash masalasi (all-pairs shortest path problem). Xar bir u tugundan xar bir v tugungacha qisqaroq yo’lni aniqlash masalasi Eng qisqa yo'lni aniqlash masalasi har hil masalalarda berilishiga qarab quyidagicha talafuzlarga ega bo’lish mumkin.