O’zbekiston respublikasi raqamli texnologiyalar vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti mustaqil ish Graflarni eniga va bo’yiga aylanish (tekshirish) Bajardi: Nuriddinov Diyorbek Guruh

k=1 dan |V| gacha bajariladi
i=1 dan |V| gacha bajariladi
j=1 dan |V| gacha bajariladi
agar D[i][k] + D[k][j]
Floyd-Uorshell algoritmi.
i tugunidan j tugunigacha eng qisqa yo'l ular orqali va boshqa tugunlar to'plamidan o'tishi mumkin k∈ (1, ..., |V|). i dan j gacha bo'lgan yo'l k tugundan o’tishi yoki o'tmasligi ham mumkin. Agar boshqa yo'l mavjud bo’lsa, u i dan k ga, keyin k dan j gacha o'tishini anglatadi, shuning uchun u qisqa yo'lning qiymati D[i][j]ni D[i][k] + D[k][j] yig'indi bilan almashtirish kerak.
Floyd-Worshell algoritmining to'liq kodini C ++ da ko'rib chiqamiz va u bajaradigan harakatlar ketma-ketligini batafsil tahlil qilamiz.
C++ da dastur kodi:
#include "stdafx.h"
#include using namespace std;
const int maxV=1000;
int i, j, n;
int GR[maxV][maxV]; // Floyd-Uorshall algoritmi
void FU(int D[][maxV], int V) int k; for (i=0; i
cout<
void main() {
setlocale(LC_ALL, "Rus");
cout<<" Grafikdagi cho'qqilar soni > ";
cin>>n;
cout<<"Chek og'irlik matritsasini kiriting:\n";
for (i=0; i<<"GR["< ";
cin>>GR[i][j];
}
cout<<"Eng qisqa yo'llar matritsasi:"<<
Kruskal algoritmi.
Ushbu algoritm 1956 yili Kruskal tomonidan ishlab chiqilgan.
Faraz qilamiz, V = {1, 2, .... n} tugunlar to‘plamidan iborat va E qirralar to‘plamida aniqlangan s narx funksiyasi bilan berilgan G= (V, E) bog‘langan graf bo‘lsin. Kruskal algoritmida G graf uchun minimal narxli daraxtlar skeletini qurish G grafning faqat n ta tugunlaridan tashkil topgan va qirralari bo‘lmagan T=(V, ø) grafdan boshlanadi. Shunday qilib, har bir tugun bog‘langan (o‘zi-o‘zi bilan) komponent hisoblanadi. Algoritm bajarilishi vaqtida bog‘langan komponentlar naboriga ega bo‘lamiz, asta-sekin birlashtirib daraxtlar skeletini tashkillashtiramiz.
Asta-sekin o‘suvchi bog‘langan komponentlarni qurishda E to‘plamdan qirralar ularning narxi o‘sishi tartibida navbatma-navbat tekshiriladi. Agar navbatdagi qirra turli komponentlardagi ikkita tugunni birlashtirsa, u holda bu qirra T grafga qo‘shiladi. Agar bu qirra bitta komponentning ikkita tugunini birlashtirsa, u tashlab yuboriladi, chunki uning bog‘langan komponentga qo‘shilishi sikl hosil bo‘lishiga olib keladi. G grafning barcha tugunlari bitta komponentga tegishli bo‘lsa, T minimal narxli daraxtlar skeletini qurish bu graf uchun tugaydi.