Page 24 - 4387

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

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

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

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

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

цієї дуги досягався мінімум відповідно до формули (3.1).

Присвоїти у=х.

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

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

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

2.

Приклад 3.1. Застосувати алгоритм Дейкстри до графа,

зображеного на рис. 3.1, для знаходження в ньому найкоротшого
шляху між вершинами v та w.

Рисунок 3.1.

Розв'язок.

Крок 1. Позначаємо вершину v. Вважаємо, що d(v)=0, d(x)=∞

для всіх вершин х, які не збігаються з v. Присвоюємо у=v.

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

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

d (a ) = min{d (a );d (v ) + c (v ,a )} = min{∞ 0 ; + } 4 = 4;

d (b ) = min{d (b );d (v ) + c (v ,b )} = min{∞ 0 ; + } 7 = 7;

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

d (d ) = min{d (d );d (v ) + ( dvc , )} = min{ ∞ 0; + ∞} = ∞;

23