Toshkent axborot texnologiyalari universiteti urganch filiali kompyuter injiniringi fakulteti

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
tugunidan j tugunigacha eng qisqa yo'l ular orqali va boshqa tugunlar to'plamidan o'tishi mumkin k∈(1, ..., |V|). i dan jgacha 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 ++ va Paskalda ko'rib chiqamiz va keyin 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];
//алгоритм Флойда-Уоршелла void FU(int D[][maxV], int V) int k; for (i=0; i
//главная функция void main() { setlocale(LC_ALL, "Rus"); cout<<"Количество вершин в графе > "; cin>>n; cout<<"Введите матрицу весов ребер:\n"; for (i=0; i<<"GR["< "; cin>>GR[i][j]; } cout<<"Матрица кратчайших путей:"<
C++ da dastur kodi:
Tasavvur qilaylik, har bir elementi vazn haqida ma’lumot saqlovchi qo’shma matritsa quyidagicha berilgan bo’lsin:
Quyidagi grafda tugunlar soni 3 ga teng va u quyidagi matrisa bilan berilgan.
Algoritm masalasi:
Matrisani shunday qayta yozish kerakki, undagi har bir element i va j tugun orasidagi qirra vaznini emas, balki I dan j gacha qisqa yo’l vaznini saqlasin. Misol uchun kichik bir graf olamiz.Shu sababli undagi qiymatlar deyarli o’zgarmasligi ham mumkin.Ammo dastur narijasida unda 2ta element qiymati almashganligini ko’rish mumkin.Quyidagi sxemada buni tahlil qilish mumkin.
C++ da dastur kodi:
Ushbu jadvalda algoritmning asosiy qismini ifodalovchi27ta bosqichi keltirilgan. Usulning bajarilish vaqti O(|V|3) bo'lganligi sababli bosqichlar soni shunchalik ko'p. Graf 3 ta tugunga ega va33=27ga teng. Birinchi o'zgarish k = 1, i = 2 va j = 3 bo’lgandagi iteratsiyada sodir bo'ladi. Bunda D[2][1]=1, D[1][3]=2, D[2][3]=4. Shart to'g'ri, ya'ni D[1][3] + D[3][2] = 3 va 3
Foydalanilgan adabiyotlar
1. Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн; пер. с англ. – 2-е изд. – М.: Вильямс, 2011. – 1 296 с.
2. Кристофидес, Н. Теория графов: Алгоритмический подход / Н. Кристофидес. – М.: Мир, 1978. – 434 с.
3. Седжвик, Р. Фундаментальные алгоритмы на С++: Алгоритмы на графах / Р. Седжвик; пер. с англ. – СПб.: Диасофт, 2002. – 496 с.
4. Скиена, С. Алгоритмы. Руководство по разработке / С. Скиена; пер. с англ. – 2-е изд. – СПб.: БХВ-Петербург, 2011.– 720 с.
5. Троелсен, Э. С# и платформа .NET 3.0, специальное издание / Э. Троелсен. – СПб.: Питер, 2008. – 1 456 с.