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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
9
v
10
p l(p)
1 ∞ ∞ ∞ ∞ 0 ∞ ∞ ∞ ∞ ∞ v
5
0
2 ∞ 5 14 20 29 ∞ 23 ∞ ∞ v
2
5
3 15 12 20 27 ∞ 23 ∞ ∞ v
3
12
4 15 20 25 ∞ 23 ∞ ∞ v
1
15
5 18 25 25 23 ∞ ∞ v
4
18
6 25 23 21 ∞ ∞ v
8
21
7 25 23 29 ∞ v
7
23
8 25 29 ∞ v
6
25
9 27 33 v
9
27
10 33 v
10
33
pred v
2
v
5
v
2
v
1
v
5
v
3
v
4
v
4
v
6
v
6
∞,
v
5
,
C,
Γ(v
5
)
l(v
i
)= min{l(v
i
), l(p)+c(p, v
i
)}.
v
2
,
Γ(v
2
)
v
3
,
v
10
.
    òàáë. 4.2 ñîäåðæàòñÿ ðåçóëüòàòû ðàñ÷åòîâ äëÿ ðàçîáðàí-
íîãî âûøå ïðèìåðà. Ïîêàæåì, êàê îíà çàïîëíÿåòñÿ.
                                                              Òàáëèöà 4.2
     Èòå
      ðà    v1   v2   v3   v4   v5        v6   v7   v8   v9   v10   p     l(p)
     öèè
       1    ∞    ∞    ∞    ∞    0     ∞        ∞    ∞    ∞    ∞     v5    0
       2    ∞    5    14   20         29       ∞    23   ∞    ∞     v2    5
       3    15        12   20         27       ∞    23   ∞    ∞     v3    12
       4    15             20         25       ∞    23   ∞    ∞     v1    15
       5                   18         25       25   23   ∞    ∞     v4    18
       6                              25       23   21   ∞    ∞     v8    21
       7                              25       23        29   ∞     v7    23
       8                              25                 29   ∞     v6    25
       9                                                 27   33    v9    27
      10                                                      33    v10   33
     pred   v2   v5   v2   v1   v5        v3   v4   v4   v6   v6

   Íà ïåðâîé èòåðàöèè ïîëàãàåì âðåìåííûå ìåòêè äëÿ âñåõ
âåðøèí, êðîìå íà÷àëüíîé, ðàâíûìè ∞, à äëÿ íà÷àëüíîé  0.
Ïîñëåäíåé ïîñòîÿííî ïîìå÷åííîé ñ÷èòàåì âåðøèíó v5 , à åå
ìåòêó ðàâíîé 0.
   Íà âòîðîé èòåðàöèè, èñïîëüçóÿ ìàòðèöó C, íàõîäèì âñå
âåðøèíû ìíîæåñòâà Γ(v5 ) è ïåðåñ÷èòûâàåì èõ âðåìåííûå ìåò-
êè ïî ôîðìóëå l(vi )= min{l(vi ), l(p)+c(p, vi )}. Ñðåäè âðåìåí-
íûõ ìåòîê èùåì ìèíèìàëüíóþ. Ýòî ìåòêà âåðøèíû v2 , òå-
ïåðü åå ñ÷èòàåì ïîñòîÿííî ïîìå÷åííîé.
   Íà òðåòüåé èòåðàöèè íàõîäèì âåðøèíû ìíîæåñòâà Γ(v2 )
è ïåðåñ÷èòûâàåì èõ âðåìåííûå ìåòêè. Ñðåäè âñåõ âðåìåííûõ
âíîâü èùåì ìèíèìàëüíóþ ìåòêó. Íà ýòîé èòåðàöèè ïîñòîÿííî
ïîìå÷åííîé ñòàíîâèòñÿ âåðøèíà v3 , è ò. ä.
   Ïðîöåññ çàêàí÷èâàåòñÿ íà äåñÿòîé èòåðàöèè, êîãäà ïîñòî-
ÿííóþ ìåòêó ïîëó÷àåò v10 . Ðåçóëüòàòû  äëèíû êðàò÷àéøèõ
ïóòåé  ñîäåðæàòñÿ â äâóõ ïîñëåäíèõ ñòîëáöàõ òàáëèöû.
   ×òîáû íàõîäèòü ñàìè ïóòè, ñôîðìèðóåì åùå îäíó ñòðî÷-
êó òàáëèöû  pred, â êîòîðîé äëÿ êàæäîé âåðøèíû ãðàôà
óêàçàíà åå ïðåäøåñòâåííèöà íà êðàò÷àéøåì ïóòè. Ñ ýòîé öå-
ëüþ â êàæäîì ñòîëáöå îòûñêèâàåì ñàìóþ íèæíþþ ñòðîêó ñ
ïðåäïîñëåäíèì çíà÷åíèåì ìåòêè. Íàïðèìåð, â ïåðâîì ñòîëá-


                                     85

Страницы