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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

m P
(4)
p
(4)
1,4
=3,
p
(4)
1,3
=2. p
(4)
1,2
=1.
D
(4)
, d
(4)
1,4
=16.
p
(4)
4,1
=4,
i := 1 n
j := 1 n
½
d
i,j
:= c
i,j
;
c
ij
=∞ p
ij
=0 p
ij
=i;
d
ii
:= 0; D P
m := 1 n
i := 1 n D
(i6=m)&(d
i,m
6=∞)
j := 1 n D
(j6=m)&(d
m,j
6=∞)
d
ij
> d
im
+d
mj
m
½
d
ij
:= d
im
+d
mj
;
p
ij
:= p
mj
;
i := 1 n
½
d
ii
< 0
D P
m -é ïîçèöèè. Ïîñëåäíÿÿ èç ïîëó÷åííûõ ìàòðèö P(4) ïîçâîëÿ-
åò ñôîðìèðîâàòü êðàò÷àéøèé ïóòü äëÿ ëþáîé ïàðû âåðøèí.
Ïóñòü, íàïðèìåð, ýòî 1 è 4, ïðè÷åì 1  íà÷àëüíàÿ, à 4  êîíå÷-
                          (4)
íàÿ âåðøèíû. Ýëåìåíò p1,4 =3, ò. å. ïðåäïîñëåäíåé âåðøèíîé
ïóòè ÿâëÿåòñÿ âåðøèíà 3.  ñâîþ î÷åðåäü, åé ïðåäøåñòâóåò
                      (4)               (4)
âåðøèíà 2, òàê êàê p1,3 =2. Íàêîíåö, p1,2 =1. Ñëåäîâàòåëüíî,
(1,2,3,4)  êðàò÷àéøèé (1;4)-ïóòü. Êàê ñëåäóåò èç ìàòðèöû
                                 (4)
D(4) , äëèíà ýòîãî ïóòè ðàâíà d1,4 =16. Ïóñòü òåïåðü 4  íà-
                                                   (4)
÷àëüíàÿ âåðøèíà ïóòè, à 1  êîíå÷íàÿ. Òàê êàê p4,1 =4, ò. å.
ïðåäïîñëåäíÿÿ âåðøèíà ñîâïàäàåò ñ íà÷àëüíîé, êðàò÷àéøèé
(4;1)-ïóòü ñîñòîèò èç äóãè, ñâÿçûâàþùåé 4 è 1.
    Ñ èñïîëüçîâàíèåì ââåäåííûõ ðàíåå îáîçíà÷åíèé ôîðìàëè-
çîâàííîå îïèñàíèå àëãîðèòìà Ôëîéäà ìîæíî ïðåäñòàâèòü òàê:
begin     {ÀËÃÎÐÈÒÌ                        ÔËÎÉÄÀ}
  for
   
      i := 1 to n do                                     { Ôîðìèðîâàíèå }
   
    ½
      for j := 1 to n do                           { íà÷àëüíûõ çíà÷åíèé }
             di,j := ci,j ;                                   { ýëåìåíòîâ }
   
            if cij =∞ then pij =0 else pij =i;                  { ìàòðèö }
        dii := 0;                                                 {DèP}
  for
       m := 1 to n do { Çàäàíèå ÷èñëà ïðîìåæóòî÷íûõ âåðøèí }
   
       for
           i := 1 to n do                  { Ïåðåáîð ñòðîê ìàòðèöû D }
   
             if (i6=m)&(di,m 6=∞)
   
         
          
   
   
   
          
          
             then
               for
   
   
   
          
          
                    j := 1 to n do{ Ïåðåáîð ñòîëáöîâ ìàòðèöû D}
   
   
   
          
                   
                      if (j6=m)&(dm,j 6=∞)
   
                   
                      then
                   
                    
          
          
                           if dij > dim +dmj          { Åñëè ïóòü ÷åðåç }
                           then
   
   
   
   
          
          
          
          
                    
                             ½ { âåðøèíó m êîðî÷å, êîððåêòèðîâàòü }
                  
                                dij := dim +dmj ;        { äëèíó ïóòè è }
   
         
                   
                    
   
                                p := p ; { ïðåäïîñëåäíþþ âåðøèíó. }
   
                         ij   mj
    for
   
   
   
      ½ i := 1 to n do
   
   
   
          if dii < 0 then Ïðåêðàòèòü ïðîöåññ;
          { Â ãðàôå îáíàðóæåí öèêë îòðèöàòåëüíîãî âåñà. }
 output (D,P )                        { Âûâîä ìàòðèö D è P }
end.     {ÀËÃÎÐÈÒÌ ÔËÎÉÄÀ}



                                    91

Страницы