4 І. Негізгі бөлім
жүктеу/скачать 3,23 Mb.
|
- Бұл бет үшін навигация:
- ІІ. ПРАКТИКАЛЫҚ ЖҰМЫС 2.1 Берілген тапсырманы шығару жолы
| 1.4. Форд Беллман алгоритмі
Қандай да бір орнатылған s шыңынан графтың басқа шыңдарына дейінгі арақашықтықты анықтайтын жалпы алгоритмді қарастырайық. Әдетте бұл алгоритмді Форд-Беллман алгоритмі деп атайды. Алгоритмнің жұмысы кезінде графта ұзындығы теріс мәнді контурлар жоқ деп болжанады. 1 BEGIN 2 FOR v ∈V DO D[v] := a[s, v]; D[s]:= 0; 3 FOR k := 1 TO n-2 DO 4 FOR v∈V \ {s} DO 5 FOR u ∈ V DO D[v] := min(D[v], D[u]+a[u, v]) 6 END; Алгоритм күрделілігі 0 (п 3 ) екендігі анық. Іс жүзінде есептеуді 4- циклдің орындалуы D[v], v ∈ V айнымалыларында ешқандай өзгеріс тудырмаған жағдайда аяқтауға болады. Бұл k Күрделілігі O(n*m) болатын алгоритм аламыз. 32-суретте Форд-Беллман алгоритмінің жұмысын бейнелейтін мысал көрсетілген. Мұнда 4,5-циклдер шыңдар номерінің өсу ретімен орындалады. ІІ. ПРАКТИКАЛЫҚ ЖҰМЫС 2.1 Берілген тапсырманы шығару жолы 1-сурет Біз 1-суретте граф арқылы берілген тапсырманың 1-ші төбеден қалған барлық төбелерге ең қысқа жолын табамыз. 2-сурет 2-суретте берілгендей бізде 1-ші төбе 0, ал қалған төбелері infinity(яғни шексіз ) болады. 3-сурет 1-ші төбеден қалған жалғасқан төбелерге жүріп өтеміз (3-сурет) 4-сурет 1-ші нүктеден шығатын ең қысқа жолды белгілеп аламыз, және сол нүктеден қалған нүктелерге жүріп өтеміз. (4-сурет) 5-сурет 5-ші суретте берілгендей келесі қысқа жолды белгілеп алып сол нүктеден қалған нүктелерге жүріп өтеміз 6-сурет Тағыда келесі қысқа жолды белгілеп сол төбелден қалған төбелерге жүріп өтеміз. (6-сурет) 7- сурет Қысқа жолды белгілеп алып сол төбеден суреттегідей басқа жолдармен салыстырамыз, яғни жүріп өтеміз. 8-сурет 8-суретте көрсетілгендей соңғы төбеге дейінгі қысқа жол және барлық төбеге жүрілген қысқа жол көрсетілген. жүктеу/скачать 3,23 Mb. Достарыңызбен бөлісу:
|