X(0)             X(1)             X(m)         X(m+1)        X(n–2)           X(n–1)         X(n)
                 x (1)



                            ...                     ...
 v(0)             x(1)                                                                      w(n)
 xin              xin−1                                    xi2                 xi1

           Ðèñ. 2.4. Ïðîöåññ ïîèñêà ïóòè ìåæäó âåðøèíàìè v è w
    Ðàññìîòðåííûé àëãîðèòì îïèñûâàåò ïðîöåññ íàõîæäåíèÿ òðàíçè-
òèâíîãî çàìûêàíèÿ à v, îòîáðàæàþùåãî äåðåâî êðàò÷àéøèõ ïóòåé, èñ-
                    ˆ
õîäÿùèõ îò ëþáîé âåðøèíû v êàê îò êîðíÿ äåðåâà.
   Àíàëîãè÷íî ìîæåò áûòü îïèñàí ïðîöåññ íàõîæäåíèÿ îáðàòíîãî òðàí-
çèòèâíîãî çàìûêàíèÿ à –v, ò. å. ìíîæåñòâà âåðøèí, èç êîòîðûõ ìîæíî
                      ˆ
ïîïàñòü â v ïî êðàò÷àéøåìó ïóòè.
                               Ïðèìåð
   Äëÿ ãðàôà G íà ðèñ. 2.5,à ïîêàçàíû ìåòêè âåðøèí, íà÷èíàÿ ñ âåðøè-
íû B, ïîëîæèòåëüíûå äëÿ òðàíçèòèâíîãî çàìûêàíèÿ Ã B è îòðèöàòåëü-
                                                    ˆ
íûå äëÿ îáðàòíîãî òðàíçèòèâíîãî çàìûêàíèÿ à –B.
                                             ˆ
 à              C(2,–1)                        á) || S ||:                         )    !
                                                                                    *    
                                                                                    +
                                     D(1,–1)
 B(0)                                                                               ,    
                                                                                    -
                                                                 ) * + , -                   ÃB
                                                                                             ˆ
       A(3,–2)               E(2)
                                                          à –B
                                                          ˆ             
 â ÃÂ:
    ˆ                                                Ö Â:
                                                     ˆ
                                    E(2)                             D(–1)                   A(–2)
                          D(1)                            B(0)
 B(0)
                 C(2)                A(3)                   C(–1)
      Ðèñ. 2.5. Ïóòè â ãðàôå ñ íàèìåíüøèì ÷èñëîì äóã äëÿ âåðøèíû Â:
       à – ãðàô ñ ìåòêàìè à B è à –B; á – ìàòðèöà ñìåæíîñòè ãðàôà S
                            ˆ      ˆ
         è çàìûêàíèé à  ˆ B è à –B; ⠖ ãðàôû çàìûêàíèé âåðøèíû Â
                              ˆ

                                                                                                  41


   Ïðèíöèïû ïîñòðîåíèÿ ìàøèííîãî àëãîðèòìà ïîèñêà òðàíçèòèâíîãî
è îáðàòíîãî òðàíçèòèâíîãî çàìûêàíèé ðàññìîòðèì íà ïðèìåðå ïîëó÷å-
íèÿ à B è à –B íà îñíîâå àíàëèçà ìàòðèöû ñìåæíîñòè ãðàôà (ðèñ. 2.5,á).
     ˆ      ˆ
    Ñïðàâà îò ìàòðèöû ñìåæíîñòè S íàõîäèòñÿ âåêòîð-ñòîëáåö äëÿ ÃÂ ,  ˆ
à âíèçó – âåêòîð-ñòðîêà äëÿ È −  . Ðàññìîòðèì ïîðÿäîê çàïîëíåíèÿ ñòîë-
áöà ÃÂ .
     ˆ
   1.  ïîçèöèþ  ñòîëáöà àçàïèñûâàåì íîëü (íà÷àëüíàÿ âåðøèíà).
                              ˆ
   2. Â ñòðîêå Â ìàòðèöû S åäèíèöà íàõîäèòñÿ â ïîçèöèÿõ, ñîîòâåò-
ñòâóþùèõ âåðøèíàì, â êîòîðûå åñòü ïóòü äëèíû 1, ïîýòîìó â ïîçèöèþ
D ñòîëáöà ÃÂ çàïèñûâàåì 1.
              ˆ
   3. Ñòðîêà D ìàòðèöû ñîäåðæèò 1 â ñòîëáöàõ, ñîîòâåòñòâóþùèõ âåð-
øèíàì, êîòîðûå îòñòîÿò â ãðàôå îò âåðøèíû D íà îäíó äóãó, à çíà÷èò,
êðàò÷àéøèé ïóòü äî íèõ îò âåðøèíû  ðàâåí 2 äóãàì.
   Åñëè â êëåòêàõ ñòîëáöà à, ñîîòâåòñòâóþùèõ åäèíè÷íûì ïîçèöèÿì
                            ˆ
ñòîëáöîâ â ñòðîêå D ìàòðèöû, óæå íàõîäÿòñÿ ÷èñëà, òî îíè íå ìåíÿþòñÿ
(Â, D), à â ïóñòûå êëåòêè Ñ è Å çàïèñûâàåì 2. Òåì ñàìûì èñêëþ÷àþòñÿ
ïåòëè (íàïðèìåð, â âåðøèíå D) è êîíòóðû (íàïðèìåð, äóãà (D,B)), è
ïðîäîëæàåòñÿ ðîñò äåðåâà êðàò÷àéøèõ ïóòåé îò âåðøèíû Â.
   4. Ïîâòîðÿåì ï. 3 äëÿ âåðøèí Ñ, Å è äðóãèõ, óâåëè÷èâàÿ äëèíó ïóòè
íà 1, äî òåõ ïîð, ïîêà ýòî âîçìîæíî.
   Àíàëîãè÷íî äåéñòâóåì äëÿ ïîëó÷åíèÿ Ã−  , íî ïðè ýòîì íåîáõîäèìî
                                            ˆ
òðàíñïîíèðîâàòü ìàòðèöó ñìåæíîñòè (ïîìåíÿòü ñòðîêè è ñòîëáöû ìåñ-
òàìè) è èñïîëüçîâàòü ðàññìîòðåííûé àëãîðèòì èëè âûïîëíÿòü àíàëèç
èñõîäíîé ìàòðèöû ïî ñòîëáöàì. ×èñëà, ïîëó÷åííûå â ñòðîêå Ã−  , äàþò
                                                              ˆ
ìèíèìàëüíûå äëèíû ïóòåé (÷èñëà äóã) èç òåõ âåðøèí, èç êîòîðûõ ìîæ-
íî ïîïàñòü â âåðøèíó B, íàïðèìåð èç âåðøèíû Å íåëüçÿ ïîïàñòü â Â
íèêàêèì ïóòåì.
     2.3.2. Îïèñàíèå àëãîðèòìà ïîèñêà òðàíçèòèâíîãî çàìûêàíèÿ
   Ìàøèííûé àëãîðèòì äîëæåí îáåñïå÷èâàòü ïîèñê òðàíçèòèâíîãî çà-
ìûêàíèÿ (âåêòîð Z) äëÿ ëþáîé íà÷àëüíîé âåðøèíû (Ê) ãðàôà. Âîçìîæ-
íûé âàðèàíò àëãîðèòìà ìîæåò âêëþ÷àòü ñëåäóþùèå îñíîâíûå øàãè.
   1. Ââîä ìàòðèöû ñìåæíîñòè S, åå ðàçìåðà (n) è íîìåðà íà÷àëüíîé
âåðøèíû (k).
   2. Óñòàíîâêà íà÷àëüíîãî çíà÷åíèÿ âåêòîðà Z â öèêëå (i=1(l)n, Zi= –1).
   3. Óñòàíîâêà Zk=0 (íà÷àëüíàÿ âåðøèíà), L=0 (ñ÷åò÷èê äëèíû ïóòè).
   4. Öèêë àíàëèçà íåîáðàáîòàííûõ âåðøèí:
42


5. { Ñ=0 ;                              (ñ÷åò÷èê îáðàáîòàííûõ âåðøèí)
6. öèêë i=1(1)n                                   (çàïîëíåíèå âåêòîðà Z)
         { åñëè (Zi≠L )            (âåðøèíà íå óäàëåíà íà äëèíó L, òî)
             { C=C+1;                           ( ïîäñ÷åò òàêèõ âåðøèí )
               ïðîäîëæåíèå öèêëà i;
             }
             èíà÷å
7.             öèêë j=1(1)n           (ïî ïîçèöèÿì ñòðîêè i ìàòðèöû S)
               {åñëè (Sij = 1 è Zj < 0 )      (âåðøèíà j âõîäèò â çàìû-
                                            êàíèå è åùå íå âêëþ÷åíà,òî)
                   Zj = L+1; (çàíåñåíèå äëèíû ïóòè äî âåðøèíû j â Zj)
8.              }                                           êîíåö öèêëà j)
9.         }                                               (êîíåö öèêëà i)
10. L=L+1;                           (èçìåíåíèå ñ÷åò÷èêà äëèíû ïóòè )
11.} ïîêà (Ñ < n);                         (íå âñå âåðøèíû îáðàáîòàíû,
                                               ïðîäîëæàòü öèêë àíàëèçà)
12. Âûâîä ðåçóëüòàòà: Z             (âåêòîð òðàíçèòèâíîãî çàìûêàíèÿ).




                                                                       43


       3. ÇÀÄÀ×È ÎÁ ÎÏÒÈÌÀËÜÍÛÕ ÐÀÑÑÒÎßÍÈßÕ
     ïðåäûäóùåé çàäà÷å ìû ñ÷èòàëè, ÷òî äëèíû âñåõ äóã ãðàôà G(V,U)
áûëè ðàâíû, íàïðèìåð L(u)=1. Ðàññìîòðèì òåïåðü ñëó÷àé, êîãäà êàæäîé
äóãå u ïîñòàâëåíî â ñîîòâåòñòâèå ÷èñëî L(u)>0, íàçûâàåìîå äëèíîé äóãè.
 çàâèñèìîñòè îò êîíêðåòíîãî ïðèëîæåíèÿ, ýòî ÷èñëî ìîæåò áûòü ìå-
ðîé ôèçè÷åñêîãî ðàññòîÿíèÿ, âðåìåíè, ñòîèìîñòè èëè äðóãîãî âàæíîãî
ïàðàìåòðà.
   Ðàññìîòðèì îáùóþ ïîñòàíîâêó çàäà÷è îá îïòèìàëüíûõ ðàññòîÿíè-
ÿõ íà ïðèìåðå çàäà÷è ñåòåâîãî ïëàíèðîâàíèÿ è óïðàâëåíèÿ (ÑÏÓ) îïå-
ðàöèÿìè, íàçûâàåìûõ òàêæå çàäà÷àìè òèïà ÏÅÐÒ ( PERT).
   Îðãðàô ÿâëÿåòñÿ åñòåñòâåííûì ñðåäñòâîì äëÿ îïèñàíèÿ è àíàëèçà
ñëîæíûõ ïðîåêòîâ, òðåáóþùèõ âûïîëíåíèÿ áîëüøîãî ÷èñëà âçàèìîñâÿ-
çàííûõ îïåðàöèé (ðàáîò). Ïðîåêòîì ìîæåò áûòü, íàïðèìåð, ïðîöåññ
ðàçðàáîòêè, ïîñòðîåíèÿ è ïðîâåðêè íåêîòîðîãî èçäåëèÿ, â òîì ÷èñëå è ñ
èñïîëüçîâàíèåì ÑÀÏÐ (ñèñòåìû àâòîìàòèçèðîâàííîãî ïðîåêòèðîâàíèÿ)
èëè ïðîöåññ ïðîåêòèðîâàíèÿ è ñòðîèòåëüñòâà çäàíèÿ, âêëþ÷àÿ ýòàïû
ïîëó÷åíèÿ è ïîäãîòîâêè ìåñòà ñòðîèòåëüñòâà.  îáùåì ñëó÷àå ïðåäïî-
ëîæèì, ÷òî ðàññìàòðèâàåòñÿ íåêîòîðûé ïðîåêò P è ìíîæåñòâî âñåõ îïå-
ðàöèé, ñâÿçàííûõ ñ âûïîëíåíèåì ïðîåêòà, ìîæíî ðàçäåëèòü íà îòäåëü-
íûå íåïåðåñåêàþùèåñÿ îïåðàöèè P{a1,a2, ... ,an}.
    Õîòÿ íåêîòîðûå îïåðàöèè ìîãóò áûòü íåçàâèñèìû äðóã îò äðóãà, â
îáùåì ñëó÷àå ìåæäó íèìè ñóùåñòâóåò çàâèñèìîñòü ïî âðåìåíè, íàïðè-
ìåð îïåðàöèÿ ai äîëæíà çàêîí÷èòüñÿ, ÷òîáû ìîãëà íà÷àòüñÿ îïåðàöèÿ aj.
Åñëè çàäàíû âñå òàêèå çàâèñèìîñòè, òî èõ óäîáíî ïðåäñòàâèòü â âèäå
îðãðàôà, êàê ïîêàçàíî íà ðèñ. 2.6. Êàæäàÿ äóãà ãðàôà ñîîòâåòñòâóåò
îäíîé îïåðàöèè, à êàæäàÿ âåðøèíà, íàçûâàåìàÿ ñîáûòèåì, ñîîòâåòñòâóåò
íåêîòîðîìó ìîìåíòó âðåìåíè.
   Äëÿ âûïîëíåíèÿ îïåðàöèè ài âûäåëÿåòñÿ íåêîòîðîå âðåìÿ t(ai), ÷òî
îòðàæåíî ÷èñëàìè íà äóãàõ ãðàôà. Äëèíà (ò. å. ñóììà âðåìåííûõ èí-
òåðâàëîâ) ëþáîãî ïóòè èç v1 â vi ñîîòâåòñòâóåò íèæíåé ãðàíèöå âðåìå-
íè, èçìåðÿåìîãî îò íà÷àëà ïðîåêòà äî íàñòóïëåíèÿ ñîáûòèÿ vi, ïîñëå

44


êîòîðîãî ìîãóò áûòü íà÷àòû îïåðàöèè, èìåþùèå vi â êà÷åñòâå íà÷àëü-
íîé âåðøèíû.
                            v"(5)           5               v$(10)

                       4                        3                          3
                                                            2
                                    2
        v(0)                                                                        v&(13)
                        3           v (3)   2           v#(8)        4
                                1                                                2
                   3
                             v!(4)                  4                    v%(8)
                Ðèñ. 3.1. Ãðàô âûïîëíåíèÿ îïåðàöèé ïðîåêòà

    Ïðè ðàñ÷åòàõ êàæäîé âåðøèíå óäîáíî ïîñòàâèòü â ñîîòâåòñòâèå ÷èñ-
ëî (âðåìÿ) ñëåäóþùèì îáðàçîì:
                       Ò(v1)=0, T(vi)=max{t(µ)} (i≠1),
ãäå t(µ) îçíà÷àåò äëèíó ïóòè è ìàêñèìóì îïðåäåëÿåòñÿ ïî âñåì ïóòÿì èç
v1 â vi.
    Äëèíîé ïóòè µ íàçûâàåòñÿ ñóììà äëèí äóã, âõîäÿùèõ â µ:

                                        L(µ) = ∑ L(u ) .
                                                u∈µ

    Äëèííåéøèé ïî âðåìåíè ïóòü îò íà÷àëüíîãî ñîáûòèÿ v1 äî êîíå÷-
íîãî ñîáûòèÿ vn íàçûâàåòñÿ êðèòè÷åñêèì ïóòåì, êîòîðûé ìîæåò áûòü
íå åäèíñòâåííûì, íàïðèìåð äëÿ ãðàôà íà ðèñ. 3.1 åñòü äâà êðèòè÷åñêèõ
ïóòè (ïî âåðøèíàì ãðàôà):
                       µ1 = (v1 , v2 , v4 , v5 , v6 , v8 ), L (µ1 ) = 13,

                        µ 2 = (v1 , v2 , v4 , v6 , v8 ), L (µ 2 ) = 13.
    Äëèíà êðèòè÷åñêîãî ïóòè ñîîòâåòñòâóåò êðàò÷àéøåìó âðåìåíè, çà
êîòîðîå ìîãóò áûòü âûïîëíåíû âñå îïåðàöèè ïðîåêòà, à çíà÷èò, è âåñü
ïðîåêò â öåëîì.
    Çàìåòèì, ÷òî ïî ñâîåé ïðèðîäå ãðàô, ïðåäñòàâëÿþùèé ïðîöåññ âû-
ïîëíåíèÿ îïåðàöèé, ÿâëÿåòñÿ àöèêëè÷åñêèì. Íàëè÷èå öèêëà ñîçäàëî áû
íåâîçìîæíóþ ñèòóàöèþ, êîãäà íè îäíà èç îïåðàöèé öèêëà íå ìîãëà áû
íà÷àòüñÿ ïåðâîé, ïîñêîëüêó ëþáàÿ èç íèõ çàâèñèò îò äðóãîé îïåðàöèè.
                                                                                              45


    Â äàëüíåéøåì ìû áóäåì ïîëüçîâàòüñÿ òåðìèíîëîãèåé, ñîîòâåòñòâó-
þùåé ðàññòîÿíèÿì, õîòÿ âñåãäà íóæíî ïîìíèòü è î äðóãèõ èíòåðïðåòà-
öèÿõ. Îòìåòèì äâå âàæíåéøèå õàðàêòåðèñòèêè äëèíû, ñóùåñòâåííûå
äëÿ äàëüíåéøåãî ðàññìîòðåíèÿ.
   1. Äëèíà äîëæíà áûòü àääèòèâíà (äëèíà ñîâîêóïíîñòè äóã ðàâíà
ñóììå äëèí îòäåëüíûõ äóã).
   2. Äëèíà äîëæíà èñïîëüçîâàòüñÿ â êà÷åñòâå öåëåâîé ôóíêöèè, êîòî-
ðóþ íåîáõîäèìî îïòèìèçèðîâàòü (ìèíèìèçèðîâàòü èëè ìàêñèìèçèðî-
âàòü) ïðè îãðàíè÷åíèÿõ íà äîïóñòèìûå ìíîæåñòâà äóã.
    Äëÿ ãðàôà ñ êîíòóðàìè (öèêëè÷åñêîãî) ìîæíî ãîâîðèòü òîëüêî î çà-
äà÷å îòûñêàíèÿ ìèíèìàëüíûõ ïóòåé ãðàôà, à â àöèêëè÷åñêîì ãðàôå ìîæíî
èñêàòü êàê ìèíèìàëüíûé, òàê è ìàêñèìàëüíûé ïóòü ìåæäó âåðøèíàìè
ãðàôà.

               3.1. Ïîèñê ìèíèìàëüíûõ ïóòåé â ãðàôå
   Ïîñòàíîâêà çàäà÷è. Äëÿ ïðîèçâîëüíîãî îðãðàôà G(V, U), ãäå äëÿ
∀u ∈U ñîïîñòàâëåíî ÷èñëî L(u) > 0 (äëèíà äóãè), íåîáõîäèìî íàéòè
ïóòü µ ìèíèìàëüíîé äëèíû, ñîåäèíÿþùèé âåðøèíó v0 c âåðøèíîé vn.
      3.1.1. Ìåòîä ðåøåíèÿ çàäà÷è ïîèñêà ìèíèìàëüíîãî ïóòè
      Ñóùåñòâóåò íåñêîëüêî ìåòîäîâ ðåøåíèÿ ýòîé çàäà÷è, ñðåäè êîòîðûõ
ðàññìîòðèì àëãîðèòì Ôîðäà, îïèñûâàåìûé ñëåäóþùèìè ïðàâèëàìè,
êîòîðûå ìîæíî ðàçäåëèòü íà äâà ýòàïà: ïðÿìîé õîä – âû÷èñëåíèå è íà-
çíà÷åíèå ìåòîê âåðøèíàì ãðàôà; îáðàòíûé õîä – îïðåäåëåíèå ìèíè-
ìàëüíîãî ïóòè.
      Ïðÿìîé õîä.
      1. Íàçíà÷åíèå íîìåðîâ âåðøèíàì. Ïåðåèìåíîâàòü âåðøèíû ãðà-
ôà G òàê, ÷òîáû èñõîäíàÿ âåðøèíà ïîëó÷èëà íîìåð 0, åñëè ýòî íåîá-
õîäèìî.
      2. Ïðèñâîåíèå íà÷àëüíûõ ìåòîê. Ïðèñâîèòü êàæäîé âåðøèíå vi ìåò-
êó λi òàê, ÷òîáû λ0 = 0, λi = ∞ ïðè i > 0 (ïîä ñèìâîëîì ∞ çäåñü ñëåäóåò
ïîíèìàòü äîñòàòî÷íî áîëüøîå ïîëîæèòåëüíîå çíà÷åíèå).
      3. Óìåíüøåíèå ìåòîê. Íàéòè òàêóþ äóãó (vi , v j ) , äëÿ êîòîðîé
λ j –λ i > L (vi , v j ) . Ó âåðøèíû v j çàìåíèòü ìåòêó λ j íà íîâóþ ìåòêó
λ ' j = λi + L (vi , v j ) , åñëè λ'j < λj.
      4. Ïåðåñ÷åò ìåòîê. Ïðèìåíÿòü ïðàâèëî 3 äî òåõ ïîð, ïîêà äëÿ êàæäîé
äóãè (vi , v j ) íå ñòàíåò ñïðàâåäëèâûì íåðàâåíñòâî λj – λi ≥ L (vi , v j ) .

46


   Îáðàòíûé õîä.
   5.  ìíîæåñòâå Ö1vn íàéòè òàêóþ âåðøèíó v p1 , ÷òî
                  λn = λp + L(vp , vn) èëè λn –λp = L(vp , vn).
                         1      1                1      1
   Àíàëîãè÷íî, â ìíîæåñòâå Ö1vp íàéòè òàêóþ âåðøèíó vp , ÷òîáû áûëî
                                    1                           2
ñïðàâåäëèâî ðàâåíñòâî
             λp = λp + L(vp ,vp ) èëè λp –λp = L(vp ,vp ) è ò. ä.
                1     2      2  1         1    2     2  1
   Ïîñëå íåêîòîðîãî ÷èñëà øàãîâ âåðøèíà vp ñîâïàäåò ñ âåðøèíîé v0.
                                                 k
   Ïóòü µ = ( v0=vp ,vp , ... ,vp , vp , vn ) – ìèíèìàëüíûé è åãî äëèíà
                     k  k–1       2    1
L(µ) = λn.
                                   Ïðèìåð
   Ïðîèëëþñòðèðóåì ðàáîòó àëãîðèòìà ïîèñêà ìèíèìàëüíîãî ïóòè äëÿ
ãðàôà íà ðèñ. 3.2.

                   v[∞,7]              4                 v"[∞,15,11]

             7                15
                                                      2            8
                                9           v![∞,9]       16                v$[∞,25,19]
   v[0]
                       5
                                                               6
                 8 7                          2   4
                                    3                                   4
                                        6
                           v [∞,8]                v#[∞,14,13]
           Ðèñ. 3.2. Îðãðàô ñ äëèíàìè äóã è ìåòêàìè âåðøèí

  Ýòàï 1 (ïðÿìîé õîä)– âû÷èñëåíèå íîâûõ ìåòîê ïðè âåðøèíàõ.
  Ïðèïèñûâàåì âåðøèíå v0 ìåòêó 0, à îñòàëüíûì âåðøèíàì – ìåòêó ∞.
Íàõîäèì íîâûå ìåòêè, êîòîðûå ïîêàçàíû â êâàäðàòíûõ ñêîáêàõ ïðè âåð-
øèíàõ ãðàôà:
  1. L(v0, v1)=7, λ'1=0+7< λ1=∞, îñòàåòñÿ λ1=7;
  2. L(v0, v2)=8, λ'2=0+8< λ2=∞, îñòàåòñÿ λ2=8;
  3. L(v0, v3)=9, λ'3=0+9< λ3=∞, îñòàåòñÿ λ3=9;
  4. L(v0, v4)=15, λ'4=0+15< λ4=∞;
  5. L(v1, v4)=4, λ'4=7+4=11< λ4=15, îñòàåòñÿ λ4=11;
  6. L(v2, v3)=3, λ'3=8+3=11 > λ3=9;

                                                                                          47


   7. L(v2, v5)=6, λ'5=8+6=14< λ5=∞,
   8. L(v3, v4)=2, λ'4=9+2=11= λ4=11,
   9. L(v3, v5)=4, λ'5=9+4=13 < λ5=14, îñòàåòñÿ λ5=13;
   10. L(v3, v6)=16, λ'6=9+16=25 < λ6=∞,
   11. L(v4, v6)=8, λ'6=11+8=19 < λ6=25,
   12. L(v5, v3)=2, λ'3=13+2=15 > λ3=9,
   13. L(v5, v6)=6, λ'6=13+6=19, îñòàåòñÿ λ6=19.
   Ýòàï 2 (îáðàòíûé õîä) – îïðåäåëåíèå ìèíèìàëüíîãî ïóòè.
   Èç âåðøèíû v6 íàõîäèì:
   1. λ6– L(v4, v6)=19–8=11=λ4,
      λ4– L(v1, v4)=11–4=7=λ1,
      λ1– L(v0, v1)=7–7=0=λ0,
çíà÷èò, ïóòü µ=( v0, v1, v4, v6) – ìèíèìàëüíûé.
   2. λ6– L(v3, v6)=19–16=3<λ3=9,
çíà÷èò, äóãà (v3, v6) íå âõîäèò â ìèíèìàëüíûé ïóòü.
   3. λ6– L(v5, v6)=19–6=13=λ5,
      λ5– L(v3, v5)=13–4=9=λ3,
      λ3– L(v0, v3)=9–9=0=λ0,
çíà÷èò, ïóòü µ = ( v0, v3, v5, v6) – ìèíèìàëüíûé.
   4. Òàê æå ìîæíî äîêàçàòü, ÷òî ïóòü µ=( v0, v3, v4, v6) – ìèíèìàëüíûé.
                3.1.2. Îáîñíîâàíèå àëãîðèòìà Ôîðäà
   Äîêàæåì, ÷òî ïîñëå êîíå÷íîãî ÷èñëà ïðèìåíåíèé ïðàâèëà 3 äëÿ êàæ-
äîé äóãè ãðàôà ñòàíåò ñïðàâåäëèâûì íåðàâåíñòâî
                        λj–λi ≤ L(vi,vj) (ïðàâèëî 4).
   Íà ëþáîì øàãå èçìåíåíèÿ ìåòêà λj>0 ïðè j≠0 (ìåòêà λ0=0), ÷òî ìîæ-
íî äîêàçàòü ïî èíäóêöèè.
   1. Äåéñòâèòåëüíî, ïðè ïåðâîì ïðèìåíåíèè ïðàâèëà 3 áóäåò èçìåíå-
íà ìåòêà λk ó îäíîé èç âåðøèí vk, ñìåæíûõ ñ âåðøèíîé v0 (vk∈Ãv0). Ýòà
âåðøèíà vk ïîëó÷èò íîâóþ ìåòêó λk = L(v0,vk)>0, íàïðèìåð v4[15].
   Ïðåäïîëîæèì, ÷òî ïîñëå ïðèìåíåíèÿ ïðàâèëà 3 m ðàç (m>1), ñòàíåò
ñïðàâåäëèâûì óòâåðæäåíèå, ÷òî λ0=0, λi>0 äëÿ i>0. Íà m+1-ì øàãå êà-
êàÿ-òî âåðøèíà vj ïîëó÷èò íîâóþ ìåòêó λj = λi + L(vi,vj). Íî â ñèëó
ïðåäïîëîæåíèÿ èíäóêöèè λi ≥ 0, êðîìå òîãî, L(vi,vj)>0, ïîýòîìó λj>0.

48


   2. Íåòðóäíî çàìåòèòü, ÷òî ïðè êàæäîì èçìåíåíèè ìåòêà âåðøèíû
ãðàôà óìåíüøàåòñÿ íà ïîëîæèòåëüíóþ âåëè÷èíó, íå ìåíüøóþ, ÷åì ìè-
íèìàëüíàÿ ðàçíîñòü äëèí ïóòåé ãðàôà.
   Èç ýòèõ äâóõ óòâåðæäåíèé ñëåäóåò, ÷òî ìåòêà ëþáîé âåðøèíû ãðàôà
ìîæåò èçìåíÿòüñÿ ëèøü êîíå÷íîå ÷èñëî ðàç. Òàê êàê âåðøèí êîíå÷íîå
ìíîæåñòâî, òî ïðàâèëî 3 ìîæåò ïðèìåíÿòüñÿ ëèøü êîíå÷íîå ÷èñëî ðàç.
   Ðàññìîòðèì îáðàòíûé ýòàï è ïîêàæåì, ÷òî, ïðèìåíÿÿ ïðàâèëî 5, ìû
ìîæåì íàéòè ìèíèìàëüíûå ïóòè.
   Äåéñòâèòåëüíî, òàê êàê â ðåçóëüòàòå ïðèìåíåíèÿ ïðàâèëà 3 ìåòêà λn
ìîíîòîííî óìåíüøàåòñÿ, òî ìû ïðèäåì ê òàêîé âåðøèíå vp (ýòî íà÷àëî
                                                        1
äóãè, ñ ïîìîùüþ êîòîðîé â ïîñëåäíèé ðàç óìåíüøèëàñü ìåòêà λn), ÷òî
               λn –λp = L(vp , vn), íàïðèìåð λ6 – λ4= L(v4, v6).
                     1      1

   Ïî ýòîé æå ïðè÷èíå íàéäåòñÿ âåðøèíà vp , äëÿ êîòîðîé ñîáëþäàåòñÿ
                                             2
ñîîòâåòñòâèå
                        λp –λp = L(vp ,vp ) è ò. ä.
                                1   2       2       1

    Ïî óñëîâèþ çàäà÷è äëèíà äóãè ãðàôà L(vi, vj)>0, ïîýòîìó ìåòêè λn,
λp , λp , ... îáðàçóþò ñòðîãî óáûâàþùóþ ïîñëåäîâàòåëüíîñòü íåîòðèöà-
  1    2
òåëüíûõ ÷èñåë, îòëè÷àþùèõñÿ äðóã îò äðóãà íà âåëè÷èíó, áîëüøóþ èëè
ðàâíóþ äëèíå êðàò÷àéøåé äóãè ãðàôà. Ñëåäîâàòåëüíî, ïðè íåêîòîðîì k
ïîëó÷èì λp = 0, vp = v0. (Âåðøèíà v0 âûäåëåíà òåì, ÷òî åé â ñèëó ïðàâè-
               k     k
ëà 1 ñ ñàìîãî íà÷àëà ïðèñâîåíà ìåòêà λ0=0 è â ôîðìèðîâàíèè ýòîé
ìåòêè íå ó÷àñòâóþò äóãè ãðàôà).
    Ïîêàæåì, ÷òî µ = ( v0=vp ,vp , ... ,vp , vp , vn ) – ìèíèìàëüíûé ïóòü ñî
                              k   k–1      2     1
çíà÷åíèåì äëèíû ïóòè L(µ)=λn, ò. å. çíà÷åíèå L( v0,vi , vi ,…,vi , vn) ëþ-
                                                            1 2    m
áîãî äðóãîãî ïóòè ìåæäó v0 è vn íå ìåíüøå λn.
    Èìååì íåðàâåíñòâà (ïî ïðàâèëó 4):
                                λi – λ0 ≤ L(v0, vi ),
                                  1                1
                                         +
                                λi –λi ≤ L(vi ,vi ),
                                  2   1        1   2
                                 ………………..,
                                         +
                                λn –λi ≤ L(vi , vn).
                                      m        m
    Ñêëàäûâàÿ ýòè íåðàâåíñòâà, ïîëó÷èì (ïðè λ0=0)
                           λn ≤ L( v0,vi , vi ,…,vi , vn).
                                        1       2       m


                                                                         49


     Â òî æå âðåìÿ ïî ïîñòðîåíèþ ïóòè µ èìååì L(µ) = λn, îòêóäà ñëåäóåò
                            L(µ) ≤ L( v0,vi , vi ,…,vi , vn),
                                             1  2     m
ò. å. µ = ( v0=vp ,vp , ... ,vp , vp , vn ) – ìèíèìàëüíûé ïóòü.
                 k   k–1       2    1
    Êàê ïîêàçàíî â ïðèìåðå, ìèíèìàëüíûé ïóòü â ãðàôå ìîæåò áûòü íå
îäèí.
               3.1.3. Ïîñòðîåíèå ìàøèííîãî àëãîðèòìà ïîèñêà
                         ìèíèìàëüíûõ ïóòåé â ãðàôå
   Èñõîäíûìè äàííûìè ÿâëÿþòñÿ ìàòðèöà ñìåæíîñòè ãðàôà äëÿ n âåð-
øèí (||S|| n×n) è ìàòðèöà äëèí äóã ãðàôà (||L|| n×n), íàïðèìåð äëÿ ãðàôà íà
ðèñ. 3.2 ýòè ìàòðèöû èìåþò âèä, ïðèâåäåííûé íà ðèñ. 3.3.

 S:                                    L:
           0    1     2   3   4   5   6                 0   1   2   3 4    5 6
       0   0    1     1   1   1   0   0             0   0   7   8   9 15   0 0
       1   0    0     0   0   1   0   0             1   0   0   0   0 4    0 0
       2   1    0     0   1   0   1   0             2   7   0   0   3 0    6 0
       3   1    0     0   0   1   1   1             3   5   0   0   0 2    4 16
       4   0    0     0   0   0   0   1             4   0   0   0   0 0    0 8
       5   0    0     0   1   0   0   1             5   0   0   0   2 0    0 6
       6   0    0     0   0   0   1   0             6   0   0   0   0 0    4 0

                    Ðèñ. 3.3. Ìàòðèöû ñìåæíîñòè è äëèí äóã ãðàôà


   Ìàòðèöà äëèí äóã ãðàôà ïî ñóòè âêëþ÷àåò âñþ èíôîðìàöèþ î ãðà-
ôå, ÷òî äåëàåò ìàòðèöó ñìåæíîñòè èçëèøíåé äëÿ äàííîé çàäà÷è. Äëÿ
ïîñòðîåíèÿ àëãîðèòìà íåîáõîäèìû âåêòîð ìåòîê âåðøèí (Ì) è ìàòðèöà
ðåçóëüòàòîâ, ñîäåðæàùàÿ âåðøèíû êðàò÷àéøèõ ïóòåé (||Ê|| n×n).
    Ïîñòðîåíèå ìàøèííîãî àëãîðèòìà îñíîâàíî íà àíàëèçå ìàòðèöû
äëèí äóã ãðàôà (L), ïîñòåïåííîì çàïîëíåíèè âåêòîðà ìåòîê âåðøèí
(Ì) íîâûìè ìåòêàìè è ïîëó÷åíèè ìàòðèöû êðàò÷àéøèõ ïóòåé (Ê).
    Â ðåçóëüòàòå âåêòîð ìåòîê (Ì) îòðàæàåò ìèíèìàëüíûå ðàññòîÿ-
íèÿ ìåæäó íà÷àëüíîé âåðøèíîé v0 è îñòàëüíûìè âåðøèíàìè. Ìàò-
ðèöà êðàò÷àéøèõ ïóòåé (Ê) îòðàæàåò èíôîðìàöèþ î ïîäãðàôå ìèíè-
ìàëüíûõ ïóòåé èñõîäíîãî ãðàôà ìåæäó íà÷àëüíîé âåðøèíîé v0 è êî-
íå÷íîé âåðøèíîé vn.
50



    

Минпросвещения России

ФГАУ ГНИИ ИТТ «Информика»

Рособрнадзор

Федеральная университетская компьютерная сеть РФ

Федеральный портал "Российское образование"

Единое окно доступа к образовательным ресурсам