Toshkent Axborot Texnalogiyalari Universiteti cal006- guruh talabasi Ilyosov Azizbekning Algaritmni loyihalash fanidan Mustaqil ish -1

for (i=0; i

cout<"<

else cout<"<

}

//asosiy funksiya

void main()

{

• int w;
• cout<<"tugunlar soni > "; cin>>n;
• e=0;
• for (i=0; i
• for (j=0; j
• {
• cout<<"Вес "<"< "; cin>>w;
• if (w!=0)
• {
• {
• edge[e].v=i;
• edge[e].u=j;
• edge[e].w=w;
• e++; } }
• cout<<"boshlang’ich tugun > "; cin>>start;
• cout<<"qisqa masofalar ro’yhati:";
• bellman_ford(n, start-1);
• system("pause>>void"); }

Floyd-Uorshell algoritmi

• Bu usulning nomlanishi 1962 yilda bir vaqtning o'zida kashf etgan ikkita amerikalik tadqiqotchilar Robert Floyd va Stiven Uorshell sharafiga qo’yilgan. Nomlanishning boshqa variantlari kamroq tarqalgan: Roy - Uorshall algoritmi yoki Roy - Floyd algoritmi. Roy - bu algoritmni hamkasblaridan 3 yil oldin (1959 yilda) ishlab chiqqan professorning familiyasidir, ammo uning kashfiyoti nashr qilimay qolgan. Floyd-Uorshell algoritmi – grafning har bir tugunigacha bo’lgan qisqa masofalarni hisoblashning dinamik algoritmidir. Bu metodni musbat va manfiy vaznga ega bo’lgan graflarda qo’llash mumkin, faqat manfiy sikllardan tashqari. Shu sababli oldin ko’rib o’tilgan Deykstra algoritmiga qaraganda umumiyroq hisoblanadi. Floyd-Uorshell algoritmini amalga oshirish uchun har bir tuguni 1 dan |V| gacha nomerlangan G=(V,E) grafning qo’shma matrisasi D[][] ni tashkil etamiz. Bu matrisa |V|x|V| o’lchamga ega bo’ladi va har bir D[i][j] elementga i dan j gacha bo’lgan qirralarning vazni o’zlashtiriladi. Algoritm bajarilishi mobaynida ushbu matrisa qayta yoziladi: uning har bir yacheykasiga i tugundan j tugungacha hisoblangan eng optimal, qisqa masofa yoziladi. Endi algoritmning asosiy qismini tuzishdan oldin, eng qisqa yo'llarning matritsasi tarkibini tushunish kerak. Uning har bir elementi D[i][j] mavjud bo'lgan marshrutlarning eng kichikini o'z ichiga olishi kerakligi sababli, biz darhol ayta olamizki, yagona tugundan uchun u nolga teng, hattoki pastadir (manfiy sikllar hisobga olinmaydi), shuning uchun asosiy diagonalning barcha elementlari (D[i][i]) ni 0 qilish kerak.

Download 341,76 Kb.