Page 47 - 4336

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

переходимо до кроку 2.

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

непозначених вершини за формулою (4.1):

d (a )  min{d (a );d (c )  c (c ,a )}  min{ 3 ; 4   }  4;

d (b )  min{d (b );d (c )  c (c ,b )}  min{ 3 ; 7   }  7 ;

d (d )  min{d (d );d (c )  c (c ,d )}  min{ 3 ;  } 3  6;

d (w )  min{d (w );d (c )  ( wcc , )}  min{  3;  }  .

Оскільки величина d(a)=4 є мінімальною з величин d(x), то

позначаємо вершину а. Так само позначаємо і дугу (v, а), яка

визначає величину d(a). Присвоюємо у=а. Поточне дерево

найкоротших шляхів складається з дуг (v, c) та (v, а) (рис. 4.4, б).

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

переходимо до кроку 2.

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

непозначених вершини за формулою (4.1):

d (b )  min{d (b );d (a )  c (a ,b )}  min{ 4 ; 7  } 3  7 ;

d (d )  min{d (d );d (a )  c (a ,d )}  min{ 4 ; 6  } 2  6;

d (w )  min{d (w );d (a )  ( wac , )}  min{  4;  }   .

Оскільки величина d(b)=6 є мінімальною з величин d(x), то

позначаємо вершину d. Можна вважати, що величину d(b)

визначають як дуга (с, d), так і дуга (a, d). Тому можна позначити

довільну із цих дуг. Позначимо, наприклад, дугу (с, d).

Присвоюємо у=d. Поточне дерево найкоротших шляхів

складається з дуг (v, c), (v, а) та (с, d) (рис. 4.4, в).

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

переходимо до кроку 2.

47