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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

C
2
n
2C
2
n
1, 2,...,n
d
(m)
ij
i
j,
m
i j d
(m)
ij
=∞.
d
(m)
ii
=0 m.
c
ij
C
i j
d
(0)
ij
, i j
d
(n)
ij
.
D
(m)
n. m=0
C D
(0)
.
D
(0)
,
D
(1)
, D
(2)
,...,D
(n)
,
D
(m)
.
d
(m)
ij
= min{d
(m−1)
ij
, d
(m−1)
im
+d
(m−1)
mj
},
i
j,
m
i j,
m−1
   Àëãîðèòì Ôëîéäà. Ýòîò àëãîðèòì îáåñïå÷èâàåò ðåøå-
íèå çàäà÷è îòûñêàíèÿ êðàò÷àéøèõ ïóòåé äëÿ âñåõ Cn2 íåóïî-
ðÿäî÷åíûõ ïàð âåðøèí ïðîñòîãî ãðàôà è âñåõ 2Cn2 óïîðÿäî÷å-
íûõ ïàð âåðøèí îðãðàôà äàæå ïðè íàëè÷èè äóã (ðåáåð) ñ îò-
ðèöàòåëüíûì âåñîì. Åäèíñòâåííûì óñëîâèåì ÿâëÿåòñÿ îòñóò-
ñòâèå â ãðàôå êîíòóðîâ (öèêëîâ) ñ ñóììàðíûì îòðèöàòåëüíûì
âåñîì. Áîëåå òîãî, àëãîðèòì ïîçâîëÿåò âûÿâèòü ýòè êîíòóðû.
   Ïðîíóìåðóåì âåðøèíû ãðàôà ÷èñëàìè 1, 2,...,n è îáîçíà-
              (m)
÷èì ÷åðåç dij äëèíó êðàò÷àéøåãî ïóòè èç âåðøèíû i â
âåðøèíó j, êîòîðûé ìîæåò ñîäåðæàòü â êà÷åñòâå ïðîìåæó-
òî÷íûõ ëþáîå ïîäìíîæåñòâî òîëüêî ïåðâûõ m âåðøèí. Åñëè
                                              (m)
ìåæäó i è j íåò ïóòè òàêîãî òèïà, ïîëàãàåì dij =∞. Åñòå-
ñòâåííî òàêæå ñ÷èòàòü, ÷òî ïðè îòñóòñòâèè â ãðàôå êîíòóðîâ
                          (m)
îòðèöàòåëüíîãî âåñà âñå dii =0 ïðè ëþáîì m. Òåïåðü ýëå-
ìåíò cij ìàòðèöû C ìîæíî ðàññìàòðèâàòü êàê äëèíó êðàò-
÷àéøåãî ïóòè èç i â j áåç ïðîìåæóòî÷íûõ âåðøèí, è îáîçíà-
       (0)
÷àòü dij , à äëèíó êðàò÷àéøåãî ïóòè ìåæäó i è j (áåç îãðà-
                                                            (n)
íè÷åíèé íà ïðîìåæóòî÷íûå âåðøèíû) îáîçíà÷àòü êàê dij .
   Ïóñòü D(m)  êâàäðàòíàÿ ìàòðèöà ïîðÿäêà n. Ïðè m=0
îíà ñîâïàäàåò ñ ìàòðèöåé C è çàïèñûâàåòñÿ êàê D(0) . Íà-
÷èíàÿ ñ D(0) , ñ ïîìîùüþ àëãîðèòìà Ôëîéäà ôîðìèðóåòñÿ
ðÿä ìàòðèö D(1) , D(2) ,...,D(n) , ïîñëåäíÿÿ èç êîòîðûõ ÿâëÿåòñÿ
èñêîìîé ìàòðèöåé äëèí êðàò÷àéøèõ ïóòåé ìåæäó âñåìè ïà-
ðàìè âåðøèí. Àëãîðèòì Ôëîéäà, êàê è àëãîðèòì Óîðøîëëà,
"ðàáîòàåò íà ìåñòå", ò. å. íå òðåáóåòñÿ õðàíèòü âñå ìàòðèöû
D(m) . Êàæäàÿ ïîñëåäóþùàÿ ìàòðèöà â ýòîì ðÿäó ïîëó÷àåòñÿ
èç ïðåäûäóùåé ñ ïîìîùüþ ïðîñòîãî ñîîòíîøåíèÿ:
               (m)         (m−1)     (m−1)     (m−1)
              dij = min{dij        , dim     +dmj      },
â îñíîâå êîòîðîãî ëåæèò ñëåäóþùåå, ïðàêòè÷åñêè î÷åâèäíîå
ïîëîæåíèå. Äëèíà êðàò÷àéøåãî ïóòè èç âåðøèíû i â âåðøèíó
j, èñïîëüçóþùåãî â êà÷åñòâå ïðîìåæóòî÷íûõ òîëüêî ïåðâûå
m âåðøèí, íå ìîæåò áûòü áîëüøå äëèíû êðàò÷àéøåãî ïóòè èç
i â j, èñïîëüçóþùåãî â êà÷åñòâå ïðîìåæóòî÷íûõ òîëüêî ïåð-
âûå m−1 âåðøèí, è íå áîëåå ñóììû äëèí äâóõ êðàò÷àéøèõ


                              87

Страницы