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

3 5 5


Şək.5.4. Şəbəkə

Yuxarıdakı şəbəkəyə minimal yol haqqında alqoritmi tətbiq etsək, aşağıdakı nəticələr alınar:

Deməli, minimal yol davamiyyəti 12 şərti zaman vahidinə bərabər olan yoldur və onun topologiyası belədir: .
Deykstra alqoritmi[2]. Yenə də şəbəkənin tillərinə t_ij çəki əmsallarının yazıldığını fərz edək, t_ij≥0, x₁ – başlanğıc düyün, x_s– sonuncu düyün olsun. Ən qısa yolun tapılması alqoritmi aşağıdakı kimi yerinə yetirilir. Hər bir düyün üçün hesablanan t_i yardımçı parametrlərdən istifadə olunur. Hesablama zamanı şəbəkənin düyünləri 2 qismə bölünür: a) açıq düyünlər b) qapalı düyünlər.
Qapalı düyünlər elə düyünlərə deyilir ki, başlanğıcdan bu düyünə qədər ən qısa yolun uzunluğu qiymətləndirilib, açıq düyünlər üçün belə qiymətləndirmə olamyıb. Hesablamanın əvvəlində yalnız x₁ düyünü qapalı düyün kimi elan olunur və t₁=0 qəbul edilir, qalan düyünlər üçün t_i = +∞; i=2,3,...,n. Alqoritm elə qurulub ki, hər iterasiyada başlanğıcdan hər hansı bir düyünə qədər ən qısa yol qiymətləndirilə bilir və həmin düyün açıq düyünlər çoxluğundan çıxarılıb qapalı düyünlər çoxluğuna daxil edilir, sonra bu düyünün varisləri qurulur. Daha sonra minorantdan açıq düyünlərə qədər yenidən qiymətləndirmə aparılır. Hansı düyünün t_i göstəricisi minimum olarsa, həmin düyün qapadılır, çünki onun başlanğıcdan minimal yolu müəyyənləşdirilmiş olur. Açıq çoxluqdan çıxarılıb qapalı çoxluğa daxil edilən düyün majorant olarsa, bunun t_i göstəricisinin qiyməti əsasında axtarılan minimal yolun davamiyyəti qiymətləndirilmiş hesab olunur. İkinci mərhələdə bu yolun topoplogiyası qurulur.
Alqoritm aşağıdakı addımlardan ibarətdir.
1 ) t_i = 0; x₁ Q (x₁-i qapalı çoxluğa aid etmək);
2) t_i = +∞; i=2,3,...,n ;
3) = x₁ qəbul etməli (cari düyün);
4) ( ,x_i tillərinin qeyd edilməsi;
5) t_i=min{t_i, t( )+ t( ,x_i)} qəbul etməli;
6) = x_i/t(x_i)= {t(x_i)};
7) Q ( düyünynü qapalı çoxluğa göndərmək);
8) əgər = x_s , onda t( ) minimal yolun uzunluğu kimi qeyd edilir və müvafiq marşrutu əks istiqamətdə (majorantdan başlayaraq minoranta tərəf) qurmaq üçün keç 9-cu addıma, ≠x_s olarsa, keç 5-ə;
9) t( )=t(x_i)+t(x_i, ) olarsa, (x_i, ) tili optimal yola aid edilir,

əks halda aid edilmir;

10) t( )=t(x_i)+t(x_i, ) şərti ödəyən x_i düyününü ilə işarə et, yəni = x_i qəbul et;
11) əgər = x₁ olarsa, son; əks halda keç 9-cu addıma.


2 4 5
8 10
1 22 4 8 7
5 2 5