Page 44 - 4336

Присвоїти d(v)=0 та d(x)=∞ для всіх х, відмінних від v.

Позначити вершину v та присвоїти у=v (у – остання з позначених

вершин).

Крок 2. Для кожної непозначеної вершини х наступним

чином перерахувати величину d(x):

d (x )  min{d (x );d (y ) c (y , x )}. (4.1)

Якщо d(x)=∞ для усіх непозначених вершин х, то закінчити

процедуру алгоритму, – у вихідному графі відсутні шляхи з

вершини v у непозначені вершини. В іншому випадку позначити

ту з вершин х, для якої величина d(x) є найменшою. Крім того,

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

цієї дуги досягався мінімум відповідно до виразу (4.1). Присвоїти

у=х.

Крок 3. Якщо у=w, то закінчити процедуру, – найкоротший

шлях з вершини v у вершину w знайдений (це єдиний шлях з v у

w, складений з позначених дуг). Якщо у≠w, то перейти до кроку

2.

Слід відзначити, що щораз, коли позначається деяка

вершина (не вважаючи вершини v), позначається і деяка дуга, що

заходить у дану вершину. Таким чином, на будь-якому етапі

алгоритму в кожну вершину заходить не більше ніж одна

позначена дуга. Крім того, позначені дуги не можуть утворювати

у вихідному графі цикл, тому що в алгоритмі не може

позначатися дуга, кінцеві вершини якої вже позначені. Отже,

можна зробити висновок про те, що позначені дуги утворюють у

вихідному графі орієнтоване дерево з коренем у вершині v. Це

дерево називається орієнтованим деревом найкоротших шляхів.

Єдиний шлях від вершини v до будь-якої вершини х, що

44