4 І. Негізгі бөлім



бет5/6
Дата09.02.2023
өлшемі3,23 Mb.
#66477
1   2   3   4   5   6
Байланысты:
практика Азизбек

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 айнымалыларында ешқандай өзгеріс тудырмаған жағдайда аяқтауға болады. Бұл kFOR u ∈ АЛДЫҢҒЫ [v] DO D[v] := min(D[v], D[u]+a[u, v]) алмастырамыз.
Күрделілігі 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-суретте көрсетілгендей соңғы төбеге дейінгі қысқа жол және барлық төбеге жүрілген қысқа жол көрсетілген.



Достарыңызбен бөлісу:
1   2   3   4   5   6




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет