Оқытушы пәнінің ОҚУ-Әдістемелік кешені

 
32-сурет. Форд-Беллман алгоритмінің жұмысы 
8.10 Дейкстра алгоритмі  
Екі маңызды жағдай үшін эффективтірек алгоритмдер бар: 
1) барлық доғалар салмақтары теріс емес; 
2) графта контурлар жоқ. 
Бірінші жағдай үшін бізге белгілі Дейкстра алгоритмі орынды болады. 
Жалпыланған түрде ол былай жазылуы мүмкін. 
1   BEGIN 
2      FOR v 
∈
 V DO D[v] := a[s, v]; D[s] := 0; 
3      T:=V\{s}; 
4     WHILE T
 DO 
≠
∅
5     BEGIN 
6         u := ерікті t 
∈
 T шыңы, D[t]=min{D[p],p
∈
T} болады; 
7        T:=T\{u}; 
8        FOR v 
∈
 Т DO D[v] - min(D[v], D[u]+a[u, v]) 
9      END 
10    END 
Алгоритмнің  жұмысын  түсіндіру  үшін 4-циклдің  инварианті  болып 
келесі шарттар келеді: 
әрбір шың үшін     
D[v]=d(s, v), v
∈
V\T 
әрбір шың үшін     
D[v]= 
s-тен v-ға 
апаратын  соңғының  алдындағы  шың V \ Т  
жиынтығына 
жататын 
жолдардың 
ең 
қысқа 
ұзындығына тең. 
Шындығында, 5-жолда [u] мәні барлығының ішіндегі t 
∈
 Т ішіндегі ең 
минималдысы болатын u 
∈
 Т шыңын табамыз. Сонымен бірге, D[u]=d(s,u). 
Бұл  шындығында  солай,  себебі,  егер s-тен u-ға  апаратын  ең  қысқа 
жолдың ұзындығы D[u] кем болса, онда (1) шартының екінші бөлігіне сәйкес 
оның  соңғысының  алдындағы  шың  Т  жиынтығына  жататын  болады. t -  
жолдың  Т  жиынтығына  жататын  бірінші  шыңы  болсын.  Біздің s-тен t-ға 
апаратын  жолдың  бастапқы  кесіндісін    s-тен t-ға  апаратын  ең  қысқа  жол 

құрайды,  сонымен  қоса,  оның  соңғысының  алдындағы  шың  Т  жиынтығына 
жатпайды.  (1) шарттың бірінші бөлігі бойынша D[t]=d(s,t). 
Салмақтардың  теріс  еместігі  туралы  болжамды  қолдана  отырып, 
алатынымыз 
D[t] 
=
 d(s, t) < d(s, u) < D[u] 
u шыңы таңдалған принципке қарама-қайшы. 
Сөйтіп D[u] = d(s, u) және  де 7-жолдан  біз (1) шартының  бірінші 
бөлігін  бұзбастан  Т  жиынтығынан u жойып  тастай  аламыз. (1) шарттың 
екінші  бөлігінің  орындалуын  қамтамасыздандыру  үшін  соңғысының 
алдындағы шың u болатын s-тен v
∈
Т апаратын жолдарды тексеру керек және 
D[v], v 
∈
 Т бағаларын анықтап алу керек. Нақ осыны 8-цикл орындайды. 
(1)  шарты 4-циклге  енгенде  орындалатыны  анық.  Т =    алгоритмінің 
жұмысы аяқталған кезде, яғни (1) шартына сәйкес, 
∅
D[v] = d(s,v), v
∈
V 
Дейкстра  алгоритмінің  күрделілігін  бағалап  көрейік. 4-цикл n-1 рет 
орындалады, оның әрбір орындалуы O(n) қадам қажет етеді: 
O(n) қадам 6-жолда u шыңын табу үшін және 
O(n) қадам 8-циклді орындау үшін. 
Сөйтіп, алгоритмнің жалпы күрделілігі O(n
2
) болады. 
Деректер құрылымының жақсы таңдалуы кезінде күрделілігі O(mlog
2
n) 
болатын алгоритмнің нұсқасын алуға болады. Ол үшін Т жиынтығын биіктігі 
O(mlog
2
n)  болатын  және  оның u мен v ерікті  шыңдары  үшін  егер u – v-нің 
ұлы  болса,  онда D[u]
≤
D[v] (2) болатын  қасиеті  бар  бинарлы  ағаш  түрінде 
көрсету керек. 
Онда D[u] минималды  болатын u шыңы  ағаштың  тамыры  болады.  Ол 
тамырдан O(log n) қадам ішінде тамырға дейінгі әрбір жолдағы D[j] мәнінің 
азаю  қасиетін  сақтай  отырып,  арылуға  болады.  Тамырды  оның  үлкен  (тең) 
мәні  бар D[j] s ұлына  алмастырып,  босаған  орынға s шыңының  үлкен D[j] 
мәнін қойған, т.с.с. жеткілікті болады. 
Егер  граф  инциденттілік  тізімдерімен  берілген  болса,  онда 8-жолды 
мынаған алмастыруға болады 
FOR v 
∈
ТІЗІМ[u] DO 
IF D[u] + a(u, v) < D[v] THEN BEGIN 
D[v] := D[u] + a(u, v); 
ағаштағы v шыңын  тамыр  бағытында (2) шартты  сақтап 
қалатындай жылжыту 
END 
Егер  біздің  ағаштың  шыңдарына  сітемелері  бар  кесте  болса,  онда v 
шыңын жылжыту O(log n) қадам ішінде жүзеге асады. 
Осындай  әдіспен  модификацияланған  алгоритмде  графтың  әрбір 
доғасы бір рет анализденеді, бұған сәйкес шыңның Т жиынтығын көрсететін 
ағашта орын ауысуына кететін O(log n) қадам саны байланысты. Қосындыда 
O(mlog n) қадам  шығады.  Осыған  біздің  ағашты  құруға  және  одан n-1 рет 
тамырды  жоюға  кететін O(nlog n) қадам  қосу  керек.  Алгоритмнің  жалпы 
күрделілігі O(mlog n). 

 
8.11 Контурсыз графтағы жолдар 
Орнатылған  шыңнан O(n
2
)  уақыт  ішінде  арақашықтықты  табу 
алгоритмі  белгілі  болоған  екінші  жағдайды,  нақтырақ  айтқанда,  граф 
контурсыз болған жағдайды қарастырайық. 
Контурсыз  ерікті  графта  әрбір  доғасы 
  түрінде,  мұнда iболғанда шыңдарды номерлеуге болады деген лемма бар. 
)
,
(
j
i
v
v
Осындай номерлеудің мысалы 33-суретте көрсетілген. 
 
33-сур. Контурсыз графтағы ең ұзын жол 
Дәлелдеу  үшін  осындай  номерлеуді  іске  асыратын  алгоритмді 
қарастырамыз. 
Бастапқы  деректер  ретінде  ТІЗІМ[v]  инциденттілік  тізімімен  берілген 
G = <V, E> графын (бағытталған, контурсыз) графты қолданамыз. Әрбір v 
∈
 
V шыңы үшін алгоритм жұмысының нәтижесі ретінде (u, v) 
∈
E доғасы үшін 
N[u]1 
BEGIN 
2 
FOR v
∈
V DO nz[v] := 0; {nz[v] – v-ға кіреті доғалар саны} 
3 
FOR u
∈
V DO 
4 
FOR у
∈
ТІЗІМ[u] DO nz[v] := nz[v]+l; 
5 
СТЕК := 0; 
6 
FOR v
∈
V 
 
DO 
7 
IF nz[v] = 0 THEN СТЕК <= v; 
8 
num := 0; 
9 
WHILE СТЕК 
∅
≠
  DO BEGIN 
10 
 u<= CTEK; 
11 
num := num + 1; N[u] := num; 
12 
FOR v 
∈
 ТІЗІМ [u] DO BEGIN 
13 
nz[v] :=nz[v]-l; 
14 
IF nz[v] = 0 THEN СТЕК <= v 
15 
END 
16 
END 
17 
END 
Алгоритм келесі фактке негізделеді: ерікті контурсыз графта бірде бір 
шың кірмейтін шың бар.