• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

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

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

Розглянемо наступну задачу: заданий скінченний орієнтований граф 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

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

Читайте також:

1. Rete-алгоритм
2. Алгоритм
3. Алгоритм
4. Алгоритм 1.
5. Алгоритм RLE
6. Алгоритм безпосередньої заміни
7. Алгоритм Берлекемпа-Мессі
8. Алгоритм відшукання оптимального плану.
9. Алгоритм Деккера.
10. Алгоритм Деккера.
11. Алгоритм діагностики при травмах живота.

Переглядів: 1787