Алгоритм Дейкстри

Алгоритм Дейкстри

Розглянемо наступну задачу: заданий скінченний орієнтований граф G, кожному ребру якого приписана його числова характеристика („довжина”). Необхідно знайти найкоротший шлях від заданої вершини (позначимо її через s) до всіх решта вершин графу.

Для розв’язання цієї задачі найбільшого розповсюдження набув алгоритм Декстри, згідно з яким всі вершини графу G (V) необхідно впорядкувати по зростанню їх відстані від вершини s:

d (s, u ₀) £ d (s, u ₁) £ … £ d (s, u_n) і V = { u ₀, u ₁, …, u_n }.

Ця послідовність будується інтеративно. Перша вершина в ній відома:

u ₀ = s; d (s, u ₀) = 0.

Нехай відомі перші (l + 1) вершини цієї послідовності:

{ u ₀ = s, u ₁, …, u_l },

які ми будемо надалі називати фіксованими. Це означає, що вершина u ₁ ближча від s, ніж всі решта (тобто нефіксовані) вершини.

Для кожної нефіксованої вершини у графу модифікуємо її відстань від s: якщо існує e (u_i, v) і d (s, u_i) + d (u_i, v) £ d (s, v), то d (s, v) = d (s, u_i) + d (u_i, v) і передостанньою вершиною в найкоротшому (на даний час) шляху, який з’єднує s з v, буде вершина u_i. Після цього серед всіх нефіксованих вершин знаходимо ту, відстань до якої від s є найменшою. Ця вершина і буде наступною в послідовності (тобто u_{i + 1}).

Масиви, що використовуються:

VID: VID(i) – найкоротша на даний момент відстань від s до i -ї вершини графу;

FIX: FIX(i) = 1, якщо i -та вершина графу є фіксованою;

PRED: PRED(i) містить передостанню вершину в найкоротшому з усіх відомих на даний момент шляхів від s до і -ї вершини графу.

1) Початкові установки.

Для початкової вершини: VID(s) = 0, FIX(s) = 0, PRED(s) = s.

Для всіх інших вершин графу: VID(v) = ¥, FIX(v) = 0, PRED(v) = v.

Біжуча вершина: u = s, i = 1.

2) Цикл по тих вершинах графу G, для яких FIX(v) = 0

якщо існує e = (u, v) і VID(u) + d (u, v) £ VID(v)

то VID(v) = VID(u) + d (u, v), PRED(v) = u.

3) Серед вершин графу G, для яких FIX(v) = 0, знаходимо ту вершину v ₀, для якої

.

4) FIX(v ₀) = 1, u = v ₀.

5) i = i + 1.

якщо i £ n,

то йти на 2).

6) Кінець.

В результаті масив VID містить найкоротші відстані від s до всіх вершин графу; по масиву PRED можна отримати найкоротший шлях від s до довільної вершини графу.

Приклад.

Рис.7

Робота алгоритму проілюстрована в табл. 5, в якій кожний рядок відповідає одному циклу роботи алгоритму. Фіксовані вершини підкреслені, а біля вершини „ u ” на кожному кроці стоїть зірочка.

Таблиця 5

i

VID

PRED

A

B

C

D

E

F

A

B

C

D

E

F

0*

∞

∞

∞

∞

∞

A

B

C

D

E

F

∞

∞

6*

A

A

C

A

E

A

7*

∞

∞

A

A

C

A

E

A

∞

8*

∞

A

A

C

A

E

A

∞

16*

A

A

C

A

D

A

∞

A

A

C

A

D

A

Найкоротший шлях від A, наприклад, до E будується, використовуючи масив PRED, таким чином: E D A.

Дата добавления: 2014-11-29