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

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:

Berilgan grafda eng qisqa masofani topish masalasining formal qo’yilishi

Eng qisqa masofa aniqlash usullari

Eng qisqa yo'lni aniqlash masalasi har hil masalalarda berilishiga qarab quyidagicha talafuzlarga ega bo’lish mumkin:
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
Berilgan punktga yetib borishning qisqaroq yo’lini aniqlash masalasi
(single-source shortest path problem).
(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

Graflarda eng qisqa yo’lni aniqlash algoritmlar tahlili

Hozirgi kunga kelib graflarda eng qisqa y’olni aniqlash uchun ko’plab algoritmlar ishlab chiqilgan. Ularni amalga oshirish masalaning berilishiga qarab foydalanish mumkin. Hayotiy masalalarida odatda vaznga ega bo’lgan graf tuzilmalarida eng qisqa yo’lni aniqlash algoritmlari qullaniladi.

Vaznga ega bo’lgan graf tuzilmasini kompyuter hotirasiga saqlash uchun quyidagi belgilanishlarini aytib o’tamiz: n – tugunlar soni; m – qirralar soni; g[n][n] – grafning qo’shma matritsasi; g[n][m] – grafning intsidientlik matritsasi; e[m] – grafning qirralar ro’yhati (uchta maydondan iborat (boshlangich va yakunlovchi tugunlar raqami va qirraning og’irlik qiymati)); w[i][j] – qirraning og’irligi (vazni, o’lchami) matritsasi; d – masofa birligi; d[n] – berilgan tugundan boshqa tugunlarga qisqa masofalar massivi; d[n][n] – tugundan boshqa tugunlarga masofalar matritsasi;