Dərs vəsaiti baki -2018 azərbaycan döVLƏt neft və SƏnaye universiteti

5.5. Şəbəkədə minimal yolların tapılması alqoritmləri

Şəbəkə - istiqamətlənmiş, konturu olmayan bir başlanğıcı və bir sonu olan qrafdır. Bu mövzu başlanğıc və sonuncu düyünlər arasında ən qısa yolların tapılmasına həsr olunub. Adətən, şəbəkənin tillərinə müəyyən çəkilərin yazılması fərz olunur, məsələn, zaman, yaxud dəyər və s.

Şəbəkə üzərində optimal yolların qurulması üsullarını iki sinfə bölmək olar: 1. istiqamətlənmiş üsullar, 2. tam seçmə üsulları[3,10].
İstiqamətlənmiş üsullar yaddaşa və vaxta qənayət etməklə daha effektivdir. Tam seçmə üsulları isə faydalı informasiyadan yararlanmayaraq variantların hamısını qurur və onlardan optimal olanı seçir, ona görə də onlar effektiv deyil. İstiqamətlənmiş axtarış üsullarından aşağıdakıları qeyd etmək olar:
-dinamik proqramlaşdırma üsulları,
- kritik yol üsulu,
- Deykstra alqoritmi və s.
Tam seçmə üsulları 2 qrupa bölünür:
-dərinliyə seçmə alqoritmi.
-eninə seçmə alqorimi.
Dinamik proqramlaşdırma alqoritmi.
1. Şəbəkənin düyünlərini başlanğıcdan sonuncu düyün istiqamətində nizamlamalı, bunun üçün:
1.1. başlanğıc düyünün ranqı 1-ə bərabər hesab olunur;
1.2. -dən çıxan bütün tilləri xəyalən silməli, bu zaman müəyyən düyünlərin giriş tilləri olmayacaq, bunların ranqını 2-yə bərabər hesab etməli. Sonra ranqı 2-yə bərabər olan bütün düyünlərin çıxış tillərini xəyalən silməli. Bu zaman giriş tili olmayan bütün düyünlərin ranqını daha bir vahid artırmalı, yəni 3-ə bərabər hesab etməli və s., bütün düyünləri bu qaydada ranqlamalı, bunları r_1, r_2, və s. ilə işarə edək;
2. şəbəkənin düyünlərini x_s sonuncudan başlayaraq əks istiqamətdə yenidən nizamlamalı:
2.1. x_s düyününün ranqı r₁^*=1 hesab olunur, x_s-ə daxil olan bütün tillər xəyalən silinir. Bu zaman çıxışı olmayan bütün düyünlərin ranqı 2-yə bərabər hesab olunur r₂^*=2;
2.2. ranqı 2-yə bərabər olan bütün düyünlərin giriş tilləri xəyalən silinir, çıxışı qalmayan bütün düyünlərin ranqı 2+1 =3 hesab olunur və s. (1-ci addıma analoji, ancaq əks istiqamətdə);
3. minorantdan (x_b-dən) başlayaraq ranqlarının artma sırası ilə hesablama zamanı aşağıdakı düsturlardan istifadə olunur:
а) ; б) ;
4. majorantdan (x_s) başlayaraq hesablama zamanı aşağıdakı düsturlardan istifadə olunur:
а) ; б) ;
5. bu hesablamalar nəticəsində minimal yolun davamiyyəti olaraq qiymətləndirilir. Bu yolun topologiyası isə şərtini ödəyən düyünlərinin minimal yola aid edilməsi ilə müəyyənləşdirilir, bu şərti ödəməyən düyünlər minimal yola aid edilmir.
Məsələn, şəkil 5.4.-də 1-ci və 6-cı düyünləri birləşdirən yollar arasında ən qısa yolun tapılmasına baxaq. Baxdığımız misalda 4 alternativ yol mövcuddur. Aydındır ki, mümkün olan yollar bunlardır:

Şəkil 5.4.-də (x_i,x_j) tilləri üzərinə t_ij çəki əmsalları yazılmışdır:
t₁₂ =2, t₁₃ =3, t₃₄ =9, t₂₄ =4, t₄₆ =6,

t₂₅ =8, t₃₅ =5, t₅₆ =7.

2 4 4
2 6
1 6
3 9 8 7