|
Алгоритм дуже простий, його реалізація представлена нижче. Алгоритм працює з вершинами як з числами. Тобто кожній вершині зіставляється число - номер представлення в масиві. Величина p - це кількість вершин. Сам алгоритм по вхідній матриці довжин дуг і заданим точкам початку і кінця шляху зберігає його в масив H. Цей масив є співвіднесеними вершинами за наступним правилом: якщо вершина v лежить на потрібному нам найкоротшому шляху, то попередня нею точка на цьому шляху записана як H[v]. Також при цьому ж умові інший масив T в значенні T[v] міститиме довжину найкоротшого шляху від точки початку до v. Також цей алгоритм оперує наступними змінними:
C - матриця довжин дуг. Її розмір C[p, p]. C[v1, v2] - містить довжину дуги від точки v1 до точки v2. Примітка: За відсутності зв'язок між цими точками відстані між ними мають бути нескінченні, а не дорівнюють нулю. Це питання розглядалося раніше.
s - початкова точка шляху в графі. Та, звідки треба знайти шлях в точку t.
t - кінцева точка шляху в графі. Це мета пошуку.
X - цей одновимірний масив служить сховищем міток, для вершин, в яких би ми вже проходили в алгоритмі.
v - поточна вершина обходу (украй динамічна змінна)
////ініціалізація і опис початкового стану змінних
Перебір значень u від 1 до p:
{
T[u] = ∞;
X[u] = 0;
}
// // триває опис НУ, окремий випадок - початкова вершина.
H[s] = 0; // немає попередній початковій вершині
T[s] = 0; // довжина шляху до неї дорівнює нулю
X[s] = 1; // і ми тут були
v = s; // встановлюємо початкову вершину, як поточну оброблювану.
Мітка M : // мітка для стрибків в коді
// // далі перебираємо усі прилеглі до поточної вершини точки, і визначаємо для них
// // мінімальна відстань, порівнюючи записане в масив T і шлях по
// // поточній вершині.
Перебір значень u від 1 до p:
{
якщо X[u]=0 і T[u] > T[v]+C[v, u] те:
{
T[u] = T[v] + C[v, u];
H[u] = v; //обов'язково запишемо попередню вершину для цього шляху
}
}
// // далі шукаємо наступну точку для обходу, грунтуючись на її відстані від
// // почала. Для наступного циклу виберемо точки, що мають найменшою шлях,
// // і цей шлях вибирається, грунтуючись на даних масиву T, де довжина
// // шляхи враховує тільки довжину зв'язків, по яких вони йдуть. Т. о.
// // перший знайдений шлях від s до t і буде найкоротшим.
l = ∞;
v = 0;
Для змінної u значення від 1 до p:
{
якщо X[u] = 0 і T[u] < l те:
{
v = u;
l = T[u];
}
}
Якщо v = 0 те:
{
exit(); //немає шляху
} інакше
Якщо v = t те:
{
exit(); //шлях знайдений, наступна вершина і кінцева
} інакше
{
X[v] = 1;
Перейти на мітку M; // новий круг
}
Якщо залишилися якісь порожні місця, рекомендую пройтися по алгоритму наново, і усвідомити його остаточно. Крок основного циклу виконує дві дії: по-перше, розставляє/оновлює знання про мінімальні шляхи сусідніх з поточною вершин, по-друге, визначає вершину для наступного кроку, яка має найкоротший шлях від початку.
Як бачите, алгоритм не зайде в пошуку далі, ніж треба, і за умови, що вершини лежать близько один до одного, результат буде отриманий дуже скоро. Проте якщо шлях "далекий", то доведеться обійти практично увесь граф. Представлений алгоритм - один з найвідоміших, простіших і дієвіших. Його також називають хвилевим алгоритмом, оскільки обхід здійснюється як би хвилями, оновлюючи прилеглі вершини.
За допомогою алгоритму Дейкстры добре шукати конкретні одноразові шляхи. Але найчастіше на ігровому полі це завдання відбувається багаторазово. Причому з різними початковими умовами. Використовувати цей же алгоритм ніхто не забороняє, але далі я пропоную вашій увазі ще один алгоритм для пошуку найкоротшого шляху. Алгоритм Флойда має схожі початкові дані, але на виході повертає двовимірний аналог масиву H[p] -> H[p][p].
|
