Элементы теории графов. Домнин Л.Н. - 68 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

p
l(v
i
) = min[l(v
i
), c
p,i
],
l(v
i
) v
i
; p
l(v
i
)
pred
v
i
, p.
T
0
v
1
.
v
1
p
C,
l(v
i
)=c
1,i
.
v
1
.
pred.
v
5
,
v
5
p
{v
5
, v
1
}.
l(v
i
)= min[l(v
i
), c
5,i
].
l(v
i
)
v
i
,
p=v
5
. l(v
2
), l(v
4
), l(v
6
) l(v
8
),
v
5
.
l(v
4
)=3,
p v
4
,
{v
4
, v
5
}.
âêëþ÷àåòñÿ âåðøèíà ñ ìèíèìàëüíîé âðåìåííîé ïîìåòêîé, êî-
òîðàÿ â äàëüíåéøåì óæå íå ìåíÿåòñÿ (â òàáëèöå âûäåëåíà
øðèôòîì). Ñàìà âåðøèíà ñ÷èòàåòñÿ ïîñòîÿííî ïîìå÷åííîé è
ôèêñèðóåòñÿ â ñòîëáöå p òàáëèöû. Ïîñëå ýòîãî ïðîèçâîäèòñÿ
ïåðåñ÷åò âðåìåííûõ ïîìåòîê âñåõ âåðøèí, ñîñåäíèõ ñ ïîñëåä-
íåé ïîñòîÿííî ïîìå÷åííîé âåðøèíîé, ïî ôîðìóëå:

                      l(vi ) = min[l(vi ), cp,i ],

ãäå l(vi )  ïîìåòêà âåðøèíû vi ; p  ïîñëåäíÿÿ ïîñòîÿí-
íî ïîìå÷åííàÿ âåðøèíà. Åñëè l(vi ) ìåíÿåò çíà÷åíèå (óìåíü-
øàåòñÿ), ñëåäóåò ñêîððåêòèðîâàòü ñîäåðæèìîå ñòðîêè pred â
ñòîëáöå vi , çàìåíèâ ïðåæíåå çíà÷åíèå íà çíà÷åíèå p.
   Ïóñòü T0 ñîñòîèò èç åäèíñòâåííîé âåðøèíû v1 . Ðàññìàò-
ðèâàÿ íà ïåðâîé èòåðàöèè v1 êàê ïîñëåäíþ ïîñòîÿííî ïîìå-
÷åííóþ, çàíîñèì åå â ñòîëáåö p ïåðâîé ñòðîêè. Èñïîëüçóÿ
ìàòðèöó C, ïðèñâàèâàåì âñåì îñòàëüíûì âåðøèíàì âðåìåí-
íûå ïîìåòêè l(vi )=c1,i . Ãîâîðÿò, ÷òî âåðøèíû ïîëó÷èëè ñâîè
ïîìåòêè èç v1 . Ôèêñèðóåì ýòî â ïîñëåäíåé ñòðîêå òàá-
ëèöû  ñòðîêå "âåðøèí-ïðåäøåñòâåííèö", îáîçíà÷åííîé êàê
pred. Çàòåì îòûñêèâàåì ìèíèìàëüíóþ âðåìåííóþ ïîìåòêó. Â
íàøåì ïðèìåðå ýòî ïîìåòêà âåðøèíû v5 , ðàâíàÿ 2. Äàëåå ñ÷è-
òàåì íàéäåííóþ ïîìåòêó ïîñòîÿííîé, à âåðøèíó v5 ïîñòîÿííî
ïîìå÷åííîé, çàïèñûâàåì åå â ñòîëáåö p è âêëþ÷àåì â ôîðìè-
ðóåìûé îñòîâ ðåáðî {v5 , v1 }. Îòìåòèì, ÷òî âåñ âêëþ÷àåìîãî
ðåáðà ðàâåí çíà÷åíèþ íàéäåííîé ïîìåòêè.
   Íà ñëåäóþùåé èòåðàöèè ïåðåñ÷èòûâàåì âðåìåííûå ïîìåò-
êè ïî ôîðìóëå l(vi )= min[l(vi ), c5,i ]. Ïðè ýòîì, åñëè çíà÷åíèå
ïîìåòêè l(vi ) ìåíÿåòñÿ (óìåíüøàåòñÿ), êîððåêòèðóåì è çíà÷å-
íèå â ïîñëåäíåé ñòðîêå ñòîëáöà vi , çàìåíÿÿ åãî òåêóùèì çíà-
÷åíèåì p=v5 . Ïîñêîëüêó èçìåíÿþòñÿ l(v2 ), l(v4 ), l(v6 ) è l(v8 ),
ñëåäóåò ñêîððåêòèðîâàòü ñîäåðæèìîå 2, 4, 6 è 8 ñòîëáöîâ ïî-
ñëåäíåé ñòðîêè, çàìåíèâ åãî íà v5 . Âíîâü îòûñêèâàåì ìè-
íèìàëüíóþ âðåìåííóþ ïîìåòêó. Òåïåðü ýòî l(v4 )=3, êîòîðàÿ
ñòàíîâèòñÿ ïîñòîÿííîé. Ñîîòâåòñòâåííî ïîñëåäíåé ïîñòîÿííî
ïîìå÷åííîé âåðøèíîé p ñòàíîâèòñÿ v4 , à â îñòîâ âêëþ÷àåòñÿ
ðåáðî {v4 , v5 }.



                                  68

Страницы