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

3 9 6


Şək.5.5. Şəbəkə

Deykstra alqoritmini şəkil 5.5 -də təsvir edilmiş şəbəkəyə tətbiq edərək minimal yolu və bunun davamiyyətini hesablayaq.

Cədvəl 5.2
Deykstra alqoritminin realizasiyasını əks etdirən informasiya

1	2	3	4	5	6	7
+(1)	+(4)	+(2)	+(3)	+(5)	+(6)	+(7)
0
	8	5	22	12	14	15
			7

Cədvəl 5.2-də qapanmış düyünlər “+” işarəsi ilə, bu işarənin yanında mötərizədə müvafiq düyünün qapanma nömrəsi göstərilib. Cədvəldən göründüyü kimi, minimal yolun davamiyyəti 15-ə bərabərdir, müvafiq yolun topologiyası budur: 1 - 3 - 4 - 7.

5.6. Şəbəkədə maksimal yolların tapılması alqoritmləri


Maksimal (ən uzun) yolun tapılması alqoritmi. Aşağıda şərh olunan alqoritmə bəzən kritik yol alqoritmi deyilir[10]. Bu alqoritm qurulanda əvvəlki alqoritmdə olduğu kimi şəbəkənin düyünlərinin iki dəfə nizamlanması tələb olunur.
1. Bir dəfə minorant düyündən başlayaraq majorant istiqamətində, bir dəfə də əksinə majorantdan başlayaraq minorant istiqamətində şəbəkənin düyünlərinin nizamlanması (ranqlanması);
2. ranqlamadan sonra soldan sağa hər bir nömrəli düyünə parametrini aşağıdakı kimi mənimsətməli:
а) ,
б) ;
3.sonuncu düyündən başlayaraq bütün düyünlərə ranqlarının artma ardıcıllığı ilə parametrini aşağıdakı qaydada hesablamalı:
а) ,
б) .
Вu hesablamalar nəticəsində qiyməti bizə kritik (yəni maksimal) yolun davamiyyətini müəyyənləşdirəcək.
4. Bu yolun quruluşunu (topologiyasını) müəyyənləşdirmək üçün əlavə işlər görmək lazımdır. Bu məqsədlə parametrindən istifadə olunur:
Bu parametr bütün real (i,j) tilləri üçün hesablanır. Əgər hansı tillər üçün bu göstəricinin qiyməti =0 olarsa, həmin til kritik yola aid edilir, əks halda bu yola aid edilmir.

Şəkil 5.4-də təsvir edilən şəbəkə və kritik yol alqoritmi əsasında hesablama aparsaq, aşağıdakı nəticələr alınar:

Beləliklə, kritik yolun topologiyası: , bunun davamiyyəti = 18 şərti zaman vahididir.

Maksimal yolu tapmaq üçün dinamik proqramlaşdırma alqoritmi yuxarıda təqdim olunan dinamik proqramlaşdırma alqoritminin (minimal yolu tapmaq üçün) analoqudur, fərq yalnız bundadır ki, hesablama düsturlarında hər yerdə “min” əvəzinə “max” əməliyyatından istifadə olunacaq.
Tapşırıq: şəkil 5.5-də təsvir edilən şəbəkənin 1 –ci və 7-ci düyünləri arasında maksimal yolu və topologiyasını dinamik proqramlaşdırma alqoritmi ilə müəyyənləşdirin.