1. Dasturiy ta’minot va uning turlari

Prima algoritmi
Algoritmning o'zi juda oddiy. Kerakli minimal skelet asta-sekin qirralarni birma-bir qo'shib quriladi. Dastlab skelet bitta tepadan iborat deb taxmin qilinadi (u o'zboshimchalik bilan tanlanishi mumkin). Keyin ushbu tepalikdan kelib chiqadigan minimal og'irlikdagi chekka tanlanadi va minimal skeletga qo'shiladi. Shundan so'ng, skelet allaqachon ikkita tepalikni o'z ichiga olgan va hozirda eng kam og'irlikdagi chekka qidiriladi va qo'shiladi, uning bir uchi tanlangan ikkita tepaning birida, ikkinchisida, aksincha, boshqa uchlari bor, bundan mustasno bu ikkitasi. Va shunga o'xshash narsalar, ya'ni har safar minimal og'irlik qirrasi izlanadi, uning bir uchi allaqachon skeletga kiritilgan tepalik bo'lib, boshqa uchi hali olinmagan va bu chekka skeletga qo'shilgan (agar shunday qirralar bir nechta bo'lsa, siz har qanday narsani oling). Bu jarayon skelet barcha tepaliklarni (yoki bir xil bo'lgan n-1 qirralarni) o'z ichiga olguncha takrorlanadi. Natijada minimal skelet quriladi. Agar grafik dastlab ulanmagan bo'lsa, unda skelet topilmaydi (tanlangan qirralarning soni n-1 dan kam bo'lib qoladi).

76. 
    Minimal yoʻlni topish masalasi
    

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) toppish 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
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;
Algoritmlar tahlilini oddiy usuldan murakkab usuliga qarab ko’rib
chiqamiz. Ularga Floyd-Uorshell, Ford-Bellman va Deykstra algoritmlari kiradi.

76.