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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

p
v
1
v
2
, v
8
v
4
.
v
10
pred(v
10
)=v
6
, pred(v
6
)=v
3
, pred(v
3
)=v
2
pred(v
2
)=v
5
. v
5
v
10
(v
5
, v
2
, v
3
, v
6
, v
10
).
p
l
pred
post
v
∗
p := s s
v∈V
(
l(v) := ∞
pred(v) := v
post(v) := 0
l(p) := 0
post(p) := 1
p6=t t
v∈Γ(p) Γ(p), }
l(p)+c
pv
< l(v) > l(p)+c
pv
, }
½
l(v) := l( p)+c
pv
pred(v) := p
v
∗
p := v
∗
post(p) := 1
d. pred(v
i
)
l(v
i
), p
öå ýòî âòîðàÿ ñòðîêà, â âîñüìîì  ïÿòàÿ. Èñêîìàÿ âåðøèíà-
ïðåäøåñòâåííèöà ñîäåðæèòñÿ â ñòîëáöå p íàéäåííîé ñòðî-
êè. Äëÿ v1 ýòî âåðøèíà v2 , à äëÿ v8  âåðøèíà v4 . Òå-
ïåðü äëÿ îïðåäåëåíèÿ ñàìîãî ïóòè äîñòàòî÷íî çàïèñàòü öå-
ïî÷êó âåðøèí-ïðåäøåñòâåííèö, íà÷èíàÿ ñ êîíå÷íîé âåðøèíû.
Òàê, äëÿ v10 èìååì: pred(v10 )=v6 , pred(v6 )=v3 , pred(v3 )=v2
è pred(v2 )=v5 . Ýòî çíà÷èò, ÷òî êðàò÷àéøèé ïóòü ìåæäó v5 è
v10 èìååò âèä (v5 , v2 , v3 , v6 , v10 ).
    Ôîðìàëèçîâàííàÿ çàïèñü àëãîðèòìà Äåéêñòðû, â êîòîðîé
èñïîëüçîâàíû îáîçíà÷åíèÿ:
    p  ïîñëåäíÿÿ ïîñòîÿííî ïîìå÷åííàÿ âåðøèíà;
    l  ìàññèâ ÷èñëîâûõ ìåòîê âåðøèí (äëèí ïóòåé);
    pred  ìàññèâ ïðåäøåñòâóþùèõ âåðøèí 13 ;
    post  ìàññèâ ïðèçíàêà ïîñòîÿíîé ìåòêè âåðøèíû;
    v ∗  âåðøèíà ñ ìèíèìàëüíîé âðåìåííîé ìåòêîé;
ìîæåò áûòü ïðåäñòàâëåíà â ñëåäóþùåì âèäå:
begin      {ÀËÃÎÐÈÒÌ ÄÅÉÊÑÒÐÛ}
  p := s           { s  ïîñëåäíÿÿ ïîñòîÿííî ïîìå÷åííàÿ âåðøèíà }
  for(v∈V do                                  { Èíèöèàëèçèðîâàòü : }
         l(v) := ∞              { ìàññèâ ÷èñëîâûõ ìåòîê âåðøèí, }
         pred(v) := v          { ìàññèâ ïðåäøåñòâóþùèõ âåðøèí, }
         post(v) := 0        { ìàññèâ ïðèçíàêà ïîñòîÿííîé ìåòêè. }
  l(p) := 0
  post(p) := 1
  whle
     
           p6=t do        { Ïîêà t íå ñòàíåò ïîñòîÿííî ïîìå÷åííîé, }
        for v∈Γ(p) do { äëÿ âñåõ âåðøèí ìíîæåñòâà Γ(p), }
     
            if l(p)+cpv < l(v)       {ìåòêè êîòîðûõ > l(p)+cpv , }
     
     
     
            then                          { âûïîëíèòü êîððåêöèþ }
     
               ½
                    l(v) := l(p)+cpv               { ñàìîé ìåòêè }
     
                   pred(v) := p { è ïðåäøåñòâóþùåé âåðøèíû }
     
        Íàéòè v ∗        { Íàéòè ìèíèìàëüíóþ âðåìåííóþ ìåòêó }
     
     
     
                ∗             { è äàëåå ñ÷èòàòü ñîîòâåòñòâóþùóþ }
      p := v
         post(p) := 1             { âåðøèíó ïîñòîÿííî ïîìå÷åííîé }
  output (l,pred )                       { Âûâîä ìàññèâîâ l è pred }
end.        {ÀËÃÎÐÈÒÌ ÄÅÉÊÑÒÐÛ}
 13 Ôîðìèðóåòñÿ ïàðàëëåëüíî ñ ìàññèâîì d. Çíà÷åíèå pred(vi ) êîððåê-
òèðóåòñÿ ïðè êàæäîì èçìåíåíèè l(vi ), ïðèíèìàÿ çíà÷åíèå, ðàâíîå p .


                                86

Страницы