48
Í.È. Ëèñòîïàä, ä.ò.í., ïðîôåññîð, çàâåäó-
þùèé êàôåäðîé èíôîðìàöèîííûõ ðàäèî-
òåõíîëîãèé Áåëîðóññêîãî ãîñóäàðñòâåííî-
ãî óíèâåðñèòåòà èíôîðìàòèêè è ðàäèî-
ýëåêòðîíèêè,
È.À. Êàðóê, ìàãèñòðàíò Áåëîðóññêîãî ãî-
ñóäàðñòâåííîãî óíèâåðñèòåòà èíôîðìàòè-
êè è ðàäèîýëåêòðîíèêè,
A.A. Õàéäåð, àñïèðàíò Áåëîðóññêîãî ãî-
ñóäàðñòâåííîãî óíèâåðñèòåòà èíôîðìàòè-
êè è ðàäèîýëåêòðîíèêè
Àëãîðèòìû ïîèñêà êðàò÷àéøåãî ïóòè è
èõ ìîäèôèêàöèÿ
 ñòàòüå ïðåäñòàâëåí îáçîð îñíîâíûõ òåíäåíöèé è ìå-
òîäîâ ïîèñêà êðàò÷àéøåãî ïóòè ïåðåäà÷è èíôîðìàöèè â ñå-
òÿõ òåëåêîììóíèêàöèé. Î ïèñàíû îñíîâíûå àëãîðèòìû è èõ
ìîäèôèêàöèÿ. Î ñîáîå âíèìàíèå óäåëåíî ìîäèôèöèðîâàííîìó
àëãîðèòìó Äåéêñòðû, ó÷èòûâàþùåìó ïðè ïîèñêå êðàò÷àéøåãî
ïóòè òðåáîâàíèÿ QoS. Î ïèñàí ñàì àëãîðèòì è ïðåäñòàâëåíà
åãî äèàãðàììà êëàññîâ.
Ââåäåíèå
Ìóëüòèñåðâèñíàÿ ñåòü äîëæíà îáëàäàòü íàäåæíîñòüþ è
îáåñïå÷èâàòü âûñîêóþ ñêîðîñòü è íèçêóþ ñòîèìîñòü ïåðåäà-
÷è äàííûõ â ðàñ÷åòå íà åäèíèöó îáúåìà èíôîðìàöèè.
Îñíîâíàÿ çàäà÷à ìóëüòèñåðâèñíûõ ñåòåé íîâîãî ïîêîëåíèÿ
çàêëþ÷àåòñÿ â îáåñïå÷åíèè ðàáîòû ðàçíîðîäíûõ èíôîðìàöèîí-
ÍÀÓ×ÍÛÅ
ÏÓÁËÈÊÀÖÈÈ
49
íûõ è òåëåêîììóíèêàöèîííûõ ñèñòåì è ïðèëîæåíèé â åäèíîé
òðàíñïîðòíîé ñðåäå, êîãäà äëÿ ïåðåäà÷è äàííûõ è ìóëüòèìå-
äèéíîãî òðàôèêà èñïîëüçóåòñÿ åäèíàÿ èíôðàñòðóêòóðà.
Ñåòü íîâîãî ïîêîëåíèÿ îòëè÷àåòñÿ íîâûìè âîçìîæíîñòÿìè:
à) óíèâåðñàëüíûì õàðàêòåðîì îáñëóæèâàíèÿ ðàçíûõ ïðè-
ëîæåíèé;
á) íåçàâèñèìîñòüþ îò òåõíîëîãèé óñëóã ñâÿçè è ãèáêîñ-
òüþ ïîëó÷åíèÿ íàáîðà, îáúåìà è êà÷åñòâà óñëóã;
â) ïîëíîé ïðîçðà÷íîñòüþ âçàèìîîòíîøåíèé ìåæäó ïî-
ñòàâùèêîì óñëóã è ïîëüçîâàòåëÿìè.
Èíòåãðàöèÿ òðàôèêà ðàçíîðîäíûõ äàííûõ è ðå÷è ïîçâî-
ëÿåò äîáèòüñÿ êà÷åñòâåííîãî ïîâûøåíèÿ ýôôåêòèâíîñòè èí-
ôîðìàöèîííîé ïîääåðæêè óïðàâëåíèÿ ïðåäïðèÿòèåì èëè
îðãàíèçàöèåé, ïðè ýòîì èñïîëüçîâàíèå èíòåãðèðîâàííîé
òðàíñïîðòíîé ñðåäû ïîçâîëÿåò ñíèçèòü èçäåðæêè íà ñîçäàíèå
è ýêñïëóàòàöèþ ñåòè. Îïòèìàëüíî ôóíêöèîíèðóþùàÿ ìóëüòè-
ñåðâèñíàÿ ñåòü èñïîëüçóåò åäèíûé êàíàë äëÿ ïåðåäà÷è äàí-
íûõ ðàçíûõ òèïîâ, ïîçâîëÿåò óìåíüøèòü ðàçíîîáðàçèå òèïîâ
îáîðóäîâàíèÿ, ïðèìåíÿòü åäèíûå ñòàíäàðòû, òåõíîëîãèè è
öåíòðàëèçîâàííî óïðàâëÿòü êîììóíèêàöèîííîé ñðåäîé.
Áàçîâûìè ïîíÿòèÿìè ìóëüòèñåðâèñíûõ ñåòåé ÿâëÿþòñÿ
îáåñïå÷åíèå òðåáîâàíèé QoS (Quality of Service) è SLA
(Service Level Agreement), òî åñòü êà÷åñòâî îáñëóæèâàíèÿ è
ñîãëàøåíèå îá óðîâíå (êà÷åñòâå) ïðåäîñòàâëåíèÿ óñëóã ñåòè.
Ïåðåõîä ê íîâûì ìóëüòèñåðâèñíûì òåõíîëîãèÿì èçìåíÿåò
ñàìó êîíöåïöèþ ïðåäîñòàâëåíèÿ óñëóã, êîãäà êà÷åñòâî ãàðàí-
òèðóåòñÿ íå òîëüêî íà óðîâíå äîãîâîðíûõ ñîãëàøåíèé ñ ïî-
ñòàâùèêîì óñëóã è òðåáîâàíèé ñîáëþäåíèÿ ñòàíäàðòîâ, íî è
íà óðîâíå òåõíîëîãèé è îïåðàòîðñêèõ ñåòåé.
Ñðåäñòâà ïîääåðæêè êà÷åñòâà îáñëóæèâàíèÿ â ñîâðåìåí-
íûõ ïðîòîêîëàõ ìàðøðóòèçàöèè â ïîñëåäíåå âðåìÿ äîñòàòî÷-
íî ñèëüíî èçìåíèëèñü, ïðåæäå âñåãî, çà ñ÷åò ïåðåñìîòðà
ìåòðèê, èñïîëüçóåìûõ ïðè âûáîðå ìàðøðóòà. Âî-ïåðâûõ, ïðî-
èñõîäèò îòêàç îò òîïîëîãè÷åñêèõ ìåòðèê ÷èñëà ïåðåïðèå-
ìîâ (hops), õàðàêòåðíîãî äëÿ ïðîòîêîëà RIP, è îñóùåñòâëÿåò-
ñÿ ïåðåõîä íà QoS-ìåòðèêè, îñíîâàííûå íà ó÷åòå îñíîâíûõ
ïîêàçàòåëåé êà÷åñòâà îáñëóæèâàíèÿ: ñêîðîñòè ïåðåäà÷è, ñðåä-
íèõ çàäåðæåê, âàðèàöèè çàäåðæåê, óðîâíÿ ïîòåðü â òðàêòàõ ïå-
ðåäà÷è ñåòè.  ðåçóëüòàòå ìàðøðóòû ïåðåäà÷è ïàêåòîâ òîãî
èëè èíîãî òðàôèêà ïðîêëàäûâàþòñÿ ñ ó÷åòîì QoS-ïîêàçàòå-
ëåé âäîëü íèõ. Âî-âòîðûõ, âñå áîëüøå ïðîòîêîëîâ ïîääåðæè-
50
âàþò òàê íàçûâàåìûå êîìïîçèòíûå (êîìáèíèðîâàííûå) ìåòðè-
êè, â ðàìêàõ êîòîðûõ ó÷èòûâàþòñÿ îäíîâðåìåííî íåñêîëüêî
îñíîâíûõ QoS-ïîêàçàòåëåé.
1. Àëãîðèòìû ïîèñêà êðàò÷àéøèõ ïóòåé
Áëàãîäàðÿ ñâîåìó øèðîêîìó ïðèìåíåíèþ, òåîðèÿ î íà-
õîæäåíèè êðàò÷àéøèõ ïóòåé â ïîñëåäíåå âðåìÿ èíòåíñèâíî
ðàçâèâàåòñÿ è èñïîëüçóåòñÿ â ðàçëè÷íûõ ñôåðàõ äåÿòåëüíîñ-
òè, íàïðèìåð, äëÿ íàõîæäåíèÿ îïòèìàëüíîãî ìàðøðóòà ìåæäó
äâóìÿ îáúåêòàìè íà ìåñòíîñòè (êðàò÷àéøèé ïóòü îò äîìà äî
óíèâåðñèòåòà), äëÿ íàõîæäåíèÿ îïòèìàëüíîãî ìàðøðóòà ïðè
ïåðåâîçêàõ, â ñèñòåìàõ àâòîïèëîòà, â ñèñòåìàõ êîììóòàöèè
èíôîðìàöèîííûõ ïàêåòîâ â ñåòè Internet è ò.ï.
Êðàò÷àéøèé ïóòü ìîæíî îïðåäåëèòü, èñïîëüçóÿ ãðàôîêîì-
áèíàòîðíûå è ïîòîêîâûå ìàòåìàòè÷åñêèå ìîäåëè. Ïðèâåäåì
ïðèìåð íåêîòîðûõ àëãîðèòìîâ íàõîæäåíèÿ êðàò÷àéøåãî ïóòè,
áàçèðóþùèõñÿ íà òåîðèè ãðàôîâ:
àëãîðèòì Äåéêñòðû (èñïîëüçóåòñÿ äëÿ íàõîæäåíèÿ îï-
òèìàëüíîãî ìàðøðóòà ìåæäó äâóìÿ âåðøèíàìè);
àëãîðèòì Ôëîéäà (èñïîëüçóåòñÿ äëÿ íàõîæäåíèÿ îïòè-
ìàëüíîãî ìàðøðóòà ìåæäó âñåìè ïàðàìè âåðøèí);
àëãîðèòì Áåëëìàíà-Ôîðäà (äëÿ íàõîæäåíèÿ êðàò÷àé-
øåãî ïóòè îò îäíîé âåðøèíû ãðàôà äî âñåõ îñòàëüíûõ);
àëãîðèòì À* (èñïîëüçóåòñÿ äëÿ íàõîæäåíèÿ ìàðøðóòà
ñ íàèìåíüøåé ñòîèìîñòüþ îò îäíîé âåðøèíû (íà÷àëüíîé) ê
äðóãîé (êîíå÷íîé), èñïîëüçóÿ àëãîðèòì ïîèñêà ïî ïåðâîìó
íàèëó÷øåìó ñîâïàäåíèþ íà ãðàôå);
àëãîðèòì Äæîíñîíà (èñïîëüçóåòñÿ äëÿ íàõîæäåíèÿ
êðàò÷àéøåãî ïóòè ìåæäó âñåìè ïàðàìè âåðøèí âçâåøåííîãî
îðèåíòèðîâàííîãî ãðàôà);
âîëíîâîé àëãîðèòì (ïåðåáîðíûé àëãîðèòì, îñíîâàííûé íà
ìåòîäå ïîèñêà â øèðèíó) íàõîäèò ïóòü ìåæäó âåðøèíàìè ãðàôà,
ñîäåðæàùåãî ìèíèìàëüíîå êîëè÷åñòâî ïðîìåæóòî÷íûõ ðåáåð);
àëãîðèòì Ãàáîâà (èñïîëüçóåòñÿ äëÿ íàõîæäåíèÿ êðàò-
÷àéøåãî ïóòè ñ ïîìîùüþ ìàñøòàáèðîâàíèÿ);
àëãîðèòì Êàðïà (èñïîëüçóåòñÿ äëÿ îòûñêàíèÿ öèêëà ñ
íàèìåíüøèì îáùèì âåñîì).
Óêàçàííûå àëãîðèòìû ëåãêî âûïîëíÿþòñÿ ïðè ìàëîì êî-
ëè÷åñòâå âåðøèí â ãðàôå. Ïðè óâåëè÷åíèè èõ êîëè÷åñòâà çà-
äà÷à ïîèñêà êðàò÷àéøåãî ïóòè óñëîæíÿåòñÿ.  ýòîé ñâÿçè àê-
51
òóàëüíîé ÿâëÿåòñÿ çàäà÷à ðàçðàáîòêè ñîáñòâåííûõ àëãîðèò-
ìîâ ïîèñêà îïòèìàëüíîãî ïóòè èëè ìîäèôèêàöèÿ ñóùåñòâóþ-
ùèõ ïîäõîäîâ íà áàçå êîìáèíèðîâàííûõ ìåòðèê.
Ðàññìîòðèì áîëåå ïîäðîáíî âûøåïåðå÷èñëåííûå ñóùå-
ñòâóþùèå àëãîðèòìû ïîèñêà êðàò÷àéøåãî ïóòè.
Àëãîðèòì Äåéêñòðû
Àëãîðèòì Äåéêñòðû (Dijkstras algorithm) [1, 2 ] àëãîðèòì
íà ãðàôàõ, èçîáðåòåííûé íèäåðëàíäñêèì ó÷åíûì Ý.Äåéêñò-
ðîé â 1959 ãîäó. Àëãîðèòì ïîçâîëÿåò íàõîäèòü êðàò÷àéøåå
ðàññòîÿíèå îò îäíîé èç âåðøèí ãðàôà äî âñåõ îñòàëüíûõ.
Àëãîðèòì ðàáîòàåò òîëüêî äëÿ ãðàôîâ áåç ðåáåð îòðèöàòåëü-
íîãî âåñà è øèðîêî ïðèìåíÿåòñÿ â ïðîãðàììèðîâàíèè è òåõ-
íîëîãèÿõ, íàïðèìåð, åãî èñïîëüçóåò ïðîòîêîë OSPF äëÿ óñò-
ðàíåíèÿ êîëüöåâûõ ìàðøðóòîâ [1, 2 ]. Àëãîðèòì Äåéêñòðû
ðåøàåò çàäà÷ó î êðàò÷àéøèõ ïóòÿõ èç îäíîé âåðøèíû äëÿ
âçâåøåííîãî îðèåíòèðîâàííîãî ãðàôà G =(V,E) ñ èñõîäíîé
âåðøèíîé s, â êîòîðîì âåñà âñåõ ðåáåð íåîòðèöàòåëüíû
(
ω
(u, v) ≥ 0 äëÿ âñåõ (u, v) ∈ E ), ãäå V ýòî íåïóñòîå ìíîæå-
ñòâî âåðøèí èëè óçëîâ; E ýòî ìíîæåñòâî ïàð (â ñëó÷àå
íåîðèåíòèðîâàííîãî ãðàôà íåóïîðÿäî÷åííûõ) âåðøèí, íàçûâà-
åìûõ ðåáðàìè.
 ïðîöåññå ðàáîòû àëãîðèòì Äåéêñòðû ïîääåðæèâàåò
ìíîæåñòâî S ⊆ V, ñîñòîÿùåå èç âåðøèí u , äëÿ êîòîðûõ
δ
(s, u )
óæå íàéäåíî (ò.å.
(, )ds
υδυ
=
). Àëãîðèòì âûáèðàåò âåðøèíó
u ∈ V \S ñ íàèìåíüøèì
du
, äîáàâëÿåò u ê ìíîæåñòâó S è
ïðîèçâîäèò ðåëàêñàöèþ âñåõ ðåáåð, âûõîäÿùèõ èç u, ïîñëå
÷åãî öèêë ïîâòîðÿåòñÿ. Âåðøèíû, íå ëåæàùèå â S, õðàíÿòñÿ â
î÷åðåäè Q ñ ïðèîðèòåòàìè, îïðåäåëÿåìûìè çíà÷åíèÿìè ôóí-
êöèè d. Ïðåäïîëàãàåòñÿ, ÷òî ãðàô çàäàí ñ ïîìîùüþ ñïèñêîâ
ñìåæíûõ âåðøèí. Êàæäîé âåðøèíå èç V ñîïîñòàâëÿåòñÿ ìåò-
êà ìèíèìàëüíîå èçâåñòíîå ðàññòîÿíèå îò ýòîé âåðøèíû äî
α
. Àëãîðèòì ðàáîòàåò ïîøàãîâî íà êàæäîì øàãå îí «ïîñå-
ùàåò» îäíó âåðøèíó è ïûòàåòñÿ óìåíüøàòü ìåòêè. Ðàáîòà àë-
ãîðèòìà çàâåðøàåòñÿ, êîãäà âñå âåðøèíû ïîñåùåíû.
Àëãîðèòì Ôëîéäà-Óîðøåëëà
Àëãîðèòì Ôëîéäà-Óîðøåëëà äèíàìè÷åñêèé àëãîðèòì
äëÿ íàõîæäåíèÿ êðàò÷àéøèõ ðàññòîÿíèé ìåæäó âñåìè âåðøè-
52
íàìè âçâåøåííîãî îðèåíòèðîâàííîãî ãðàôà. Ðàçðàáîòàí â
1962 ãîäó Ðîáåðòîì Ôëîéäîì è Ñòèâåíîì Óîðøåëëîì [2 , 3].
Êðàòêîå îïèñàíèå àëãîðèòìà. Ïóñòü âåðøèíû ãðàôà
G =(V,E), V = n ïðîíóìåðîâàíû îò 1 äî n è ââåäåíî îáîçíà-
÷åíèå
k
ij
d
äëÿ äëèíû êðàò÷àéøåãî ïóòè îò i äî j, êîòîðûé êðî-
ìå ñàìèõ âåðøèí i, j , ïðîõîäèò òîëüêî ÷åðåç âåðøèíû 1k.
Î÷åâèäíî, ÷òî
0
ij
d
äëèíà (âåñ) ðåáðà (i, j ), åñëè òàêîâîå ñó-
ùåñòâóåò (â ïðîòèâíîì ñëó÷àå åãî äëèíà ìîæåò áûòü îáîçíà-
÷åíà êàê ∞).
Ñóùåñòâóåò äâà âàðèàíòà çíà÷åíèé
k
ij
d
, k ∈ (1,, n):
1. Êðàò÷àéøèé ïóòü ìåæäó i, j íå ïðîõîäèò ÷åðåç âåðøè-
íó k, òîãäà
1kk
ij ij
dd
−
=
.
2 . Ñóùåñòâóåò áîëåå êîðîòêèé ïóòü ìåæäó i, j , ïðîõîäÿ-
ùèé ÷åðåç k, òîãäà îí âíà÷àëå èäåò îò i äî k, à ïîòîì îò k
äî j.  ýòîì ñëó÷àå, î÷åâèäíî,
11kk k
ij ij kj
dd d
−−
=+
.
Òàêèì îáðàçîì, äëÿ íàõîæäåíèÿ çíà÷åíèÿ ôóíêöèè äîñ-
òàòî÷íî âûáðàòü ìèíèìóì èç äâóõ îáîçíà÷åííûõ çíà÷åíèé.
Òîãäà ðåêóððåíòíàÿ ôîðìóëà äëÿ
k
ij
d
èìååò âèä:
0
ij
d
äëèíà ðåáðà (i, j );
11 1
min( , )
kkkk
ij ij ik kj
dddd
−− −
=+
.
Àëãîðèòì Ôëîéäà-Óîðøåëëà ïîñëåäîâàòåëüíî âû÷èñëÿåò
âñå çíà÷åíèÿ
k
ij
d
, ∀ i, j äëÿ k îò 1 äî n. Ïîëó÷åííûå çíà÷å-
íèÿ
n
ij
d
ÿâëÿþòñÿ äëèíàìè êðàò÷àéøèõ ïóòåé ìåæäó âåðøè-
íàìè i, j .
Àëãîðèòì Áåëëìàíà-Ôîðäà
Ïðåäëîæåí íåçàâèñèìî Ðè÷àðäîì Áåëëìàíîì è Ëåñòå-
ðîì Ôîðäîì [4]. Àëãîðèòì Áåëëìàíà-Ôîðäà àëãîðèòì ïî-
èñêà êðàò÷àéøåãî ïóòè âî âçâåøåííîì ãðàôå. Àëãîðèòì íà-
õîäèò êðàò÷àéøèå ïóòè îò îäíîé âåðøèíû ãðàôà äî âñåõ
îñòàëüíûõ.  îòëè÷èå îò àëãîðèòìà Äåéêñòðû, àëãîðèòì Áåë-
ëìàíà-Ôîðäà äîïóñêàåò ðåáðà ñ îòðèöàòåëüíûì âåñîì.
