Page 33 - 4387
P. 33

Крок  2.  (y=d).  Розраховуємо  величину  d(x)  для  кожної  з

            вершини (крім вершини d) за формулою (3.1):

                    d (a ) = min{d   (a );d (d ) + c (d ,a )} = min{    ; 0 − 3 ∞+  } =  0;

                    d (b ) =  min{d  (b );d (d ) + c (d ,b )} =  min{−    ; 4 − 3 ∞+  } =  − 4;


                    d (c ) =  min{d  (c );d (d ) + c (d ,c )} =  min{  ; 4 − 3+  } 8 =  4;

                    d (e ) =  min{d  (e );d (d ) + c (d ,e )} = min{−     ; 3 − 3+ (− 2 )} = − 5.

                   Для раніше позначених вершин значення d(x) не змінилось,

            тому  позначки  з  них  не  знімаємо.  Залишилась  тільки  одна

            непозначена вершина e, яку позначаємо на даному кроці, а також

            позначаємо  дугу  (d,  e).  Присвоюємо  у=e.  Поточне  дерево

            найкоротших  шляхів  складайся  з  дуг  (a,  c),  (c,  b),  (b,  d),  (d,  e)

            (рис. 4.2 д).

                   Крок  3.  Оскільки  позначені  усі  вершини,  то  здійснюємо

            перехід до кроку 2 для того, щоб спробувати зменшити значення

            d(x) для позначених вершин.

                   Крок  2.  (y=e).  Розраховуємо  величину  d(x)  для  кожної  з

            вершини (крім вершини e) за формулою (3.1):

                    d (a ) =  min{d  (a );d  (e ) + c (e ,a )} = min{   ; 0 − 5 ∞+  } = 0;

                    d (b ) =  min{d  (b );d (e ) + c (e ,b )} = min{−    ; 4 − 5 +  } 3 =  − 4;


                    d (c ) =  min{d  (c );d (e ) + c (e ,c )} =  min{  ; 4 − 5 ∞+  } = 4;

                    d (d ) =  min{d   (d );d (e ) + c (e ,d )} = min{−    ; 3 − 5 ∞+  } =  − 3.

                   Для всіх позначених вершин значення d(x) не змінилось.

                   Крок  3.  Оскільки  позначені  усі  вершини  графа  і  на

            попередньому кроці алгоритму для жодної з позначених вершин

            не  вдалось  зменшити  значення  d(x),  то  процедура  алгоритму

            завершується.  Найкоротший  шлях  з  вершини  a  у  вершину  e

            складається  з  дуг  (a,  c),  (c,  b),  (b,  d),  (d,  e)  (рис.  4.2  д)  і  має

            довжину d(e)=-5.



                                                        32
   28   29   30   31   32   33   34   35   36   37   38