Page 60 - 4336
P. 60

1
                Елементи матриці D , d           i 1 , j    min  d 0 1 , i    d 0 , 1 j ;d i 0     Відповідні
                                                                              , j
                                                                                          шляхи

              d 1 1 , 3   d 0 1 , 3    6                                                 (3, 1)



              d 1  2 , 3   min  d 0 1 , 3   d 0 2 , 1  ;d 0 2 , 3   min   6  5 ; 1   5    (3, 2)



              d 1  3 , 3    0                                                                -


              d 1 4 , 3   min  d 0 1 , 3   d 0 4 , 1  ;d 0 4 , 3   min   6  2 ; 1   2    (3, 4)



              d 1 1 , 4   d 0 1 , 4   1                                                  (4, 1)



              d 1  2 , 4   min  d 0 1 , 4   d 0 2 , 1  ;d 0 2 , 4   min   11  ;  2    (4, 1, 2)



              d 1  3 , 4   min  d 0 1 , 4   d 0 3 , 1  ;d 0 3 , 4   min   1  4 ; 2   3    (4, 3)


              d 1  4 , 4    0                                                                -





                   Матриця  D   та  матриця  найкоротших  шляхів  D   для


            елементів матриці D є наступними:
                           0    1   2    1                               ) 2 , 1 (  ) 3 , 1 (   ) 4 , 1 (


                    D 1    2   0   4    3  ,    D    1     ) 1 , 2 (                ) 3 , 1 , 2 (  ) 4 , 1 , 2 (  .
                           6    5   0    2                    ) 1 , 3 (   ) 2 , 3 (             ) 4 , 3 (

                           1    2   3    0                    ) 1 , 4 (     ) 2 , 1 , 4 (  ) 3 , 1 , 4 (  

                   Крок 2. m=2.


                                          2
             Елементи матриці D , d            i 2 , j    min  d 1 2 , i   d 1 , 2 j ;d 1 , j   Відповідні
                                                                            i
                                                                                        шляхи

             d 2 1 , 1    0                                                                -



             d 2 2 , 1   d 1 2 , 1   1                                                 (1, 2)


             d  2 3 , 1    min  d 1 2 , 1   d 1  3 , 2  ;d 1 3 , 1   min  1  2 ; 4   2    (1, 3)




                                                        60
   55   56   57   58   59   60   61   62   63   64   65