p>
- множини вузлів мережі, з'єднаних з Вузли безлічі Ck после виконан k-й ітерації цього алгоритму.
Крок 0. Думаємо C0=і=N.
Крок1. Вібіраємо будь-який вузол і З множини візначаємо C1={i}, тоді=N- {i}. Думаємо k=2.
Основний крок k. У множини вібіраємо вузол j *, что з'єднаній самою короткою дугою з Яким-небудь Вузли з множини Ck - 1. Вузол j * прієднується до множини Ck - 1 і відаляється з множини. Таким чином, Ck=Ck - 1 + {j *},=- {j *}.
Если множини порожня, то виконан алгоритмом закінчується. У противному випадка думаємо k=k + 1 і повторюємо Последний шаг.
. 4 Алгоритм Дейкстри
Алгоритм Дейкстри вірішує задачу про найкоротшій шлях з однієї вершини в зваження орієнтованому графові G=(V, Е) у тому випадка, коли ваги ребер НЕ негатівні.
Існують две реализации алгоритмом: для поиска найкоротшого шляху между двома парами вершин и от однієї вершини до усіх других. Розглянемо реалізацію Першого алгоритмом на Основі списку суміжніх вершин
Особливості програмної реализации:
· Нумерація вершин - цілі числа, починаючі з 0
· Список вершин увазі реалізовується у виде двовімірної матриці з 3 стовпців. Коженая рядок матриці опісує вершину. У 0 стовпці Збереження статус вершини (тимчасова/Постійна/перевірена Постійна). У 1 стовпці зберігаємо компоненту відстані. У 2-му стовпці - номер попередньої вершини.
· Нескінченність Представляємо як очень ровері число (на порядок более суми усіх ребер графа)
Терміни:
Тимчасова вершина (0): вершина графа, до якої Вже відомій Який-небудь шлях
Постійна вершина (1): вершина графа, до якої Вже відомій мінімальній шлях
Перевірена Постійна вершина (2): вершина графа, до якої Вже відомій мінімальній шлях и прораховані усі шляхи до суміжніх вершин
Початкові установки:
Кожній вершіні графа ставімие у відповідність впорядкованим пару. Перша координата парі: відстань від початкової вершини до поточної вершини. Друга координата парі: Попередній вузол в дорозі від качана до цієї вершини.
Алгоритм.
) ПОЧИНАЄМО у вузлі. У списку вершин прівласнюємо Їй значення (0, 0) i робимо ее постійною.
) Основний крок. Для останньої вершини, візначеної як постійну, оцінюємо відстані з качана шляху через постійну вершину k до усіх суміжніх вершин. Для цього знаходімо торбу m и ваги ребра t З вершин vk до суміжної вершини vs и порівнюємо з наявний значень у списку вершин. Если отриманий шлях менший за наявний, прівласнюємо вершіні vs значення (m + t, k). Статус вершини vs Встановлюємо як тимчасова вершина.
) Для усіх Тимчасових вершин виконуємо поиск мінімального значення відстані з качана в поточних вершину. Перша тимчасова вершина з мінімальною відстанню отрімує статус постійною.
) Если остання Постійна вершин не кінцева, Переходимо до пункту 2. Інакше відстань, прісвоєна Їй, є мінімальною відстанню между завданні вершинами
) Для знаходження шляху необходимо початиться з кінцевої вершини и переглядаті список вершин у зворотню порядком, поки НЕ доберемося в качан.
Примітка: если при поиска наступної постійної вершини Мінімальна відстань рівна умовної нескінченності або Тимчасових вершин немає, це означає что шляху НЕ існує.
. 5 Модель Флойда-Уоршалла
Розглянемо Завдання про поиск найкоротшіх Шляхів между усіма парами вершин в орієнтованому графові G=(V, Е). Година роботи отриманий в результате алгоритмом, відомого як алгоритм Флойда-Уоршалла (Floyd - Warshall algorithm), Рівно? (V3). Наявність ребер з негативною вагою допускається, но передбачається, что цикли з негативною вагою відсутні.
У цьом алгорітмі мережа представлена ??у виде квадратної матриці з n рядками и n стовпцямі. Елемент (i, j) дорівнює відстані dij від Вузли i до Вузли j, что має кінцеве значення, если існує дуга (i, j), и дорівнює нескінченності в противному випадка.
Покажемо спочатку основнову ідею методу Флойда-Уоршалла. Нехай є три Вузли i, j и k и задані відстані между ними (рисунок 2.1). Если віконується нерівність dij + djk lt; dik, то доцільно замініті шлях i ® k путем i ® j ® k. Така заміна (далі ее будемо умовно назіваті трикутна оператором) віконується автоматично в процессе виконан алгоритмом Флойда.
Рисунок 2.1 - трикутна оператор
Алгоритм Флойда-Уоршалла требует виконан Наступний Дій.
Крок 0. Візначаємо початково матрицю відстаней D0 и матрицю послідовності вузлів S0. Діагональні елементи обох матриць позначаються знаком - raquo ;, что показує, что ЦІ елементи в Обчислення не берут...
