"justify"> З 9 клітин, виключаючи стартову, додану в закритий список, у відкритому списку залишилося 8, наступної клітиною є клітина, яка перебуває праворуч від стартової, тому у неї найменший шлях F (F=40).
Спочатку видаляємо її з відкритого списку і додаємо в закритий. Потім ми перевіряємо сусідні клітини. Клітини, відразу праворуч від цієї клітини - стіни, тому їх ігноруємо. Клітка, прямо зліва - стартова клітина. Вона знаходиться в закритому списку, тому її теж ігноруємо.
Решта 4 клітини вже знаходяться у відкритому списку, тому потрібно перевірити, чи не коротше чи шляху до цим клітинам, через поточну. Порівняння відбувається за вартістю G. Давайте подивимося на клітку, прямо під нашою обраної кліткою. Її вартість G дорівнює 14. При русі через до цієї клітці через поточну її вартість G буде дорівнює 20 (10, вартість G щоб дістатися до поточної клітці плюс 10 для руху вертикально вгору, до сусідній клітці). G=20 gt; G=14, потомуметка залишається прежней.То є більш доцільним буде рух по діагоналі на одну клітку, ніж рух на одну клітку по горизонталі, а потім одну по вертикалі.
Після повтору цих дії для всіх 4-х сусідніх клітин, які знаходяться у відкритому списку, дізнаємося, що жоден з шляхів не покращиться при русі по цим клітинам через обрану, тому їх мітки залишаються колишніми. Тепер, коли всі сусідні клітини розглянуті, можна переходити до наступної.
У якості наступної потрібно вибрати клітку з меншою вартістю F з решти 7 у відкритому списку. На даний момент найменшу вартість F=54імеют 2 клітини, для алгоритму не має значення, яку з них вибирати, зате це є причиною того, що різні реалізації алгоритму можуть знаходити однаково короткі, але різні за суттю шляху в одній задачі. У нашому випадку, навмання виберемо клітку, що знаходиться праворуч знизу від початкової, як показано на малюнку.
Клітка праворуч (стіна) і клітина праворуч знизу пропускаються (праворуч знизу пропускається через те, що її НЕ досягти без зрізу стіни, залежить від умови задачі).
Залишається ще 5 клітин. 2 клітини, які знаходяться під поточної, ще не у відкритому списку, тому їх додаємо у відкритий список і призначаємо поточну клітку їх батьком raquo ;. З 3-х інших клітин 2 вже знаходяться в закритому списку (стартова клітка і клітина, прямо над нею, на діаграмі обидві підсвічені блакитним кольором) їх ігноруємо. Остання клітина, яка знаходиться прямо зліва від поточної, перевіряється на довжину шляху по поточній клітці через цю клітку за вартістю G. Шлях не стане коротшим Пришпилька не меняется.Все сусідні клітини розглянуті, можна переходити до наступної.
Крок 4 - N - 1. Повторюємо цей процес до тих пір, поки не додамо цільову клітку у відкритий список. До кінцевого кроці повинна вийти схема схожа на наведену на малюнку.
Можна помітити, що батьківська клітина, для клітини знаходиться на 2 клітини під стартовою змінилася. До цього її батьком була клітка справа зверху, і вартість дорівнювала 28. Після перерахунку, виявилося, що до неї існує коротший шлях, рівний 20, через вершину зверху (тепер туди направлений покажчик) .Стоимость F також змінилася.
Крок N. Останнім кроком є ??визначення шляху. Починаючи пошук з кінцевої точки будемо рухатися за вказівниками на батька, поступово доходячи до початкової вершини, пройдені клітини й будуть найкоротшим шляхом.
. ПРАКТИЧНЕ ЗАСТОСУВАННЯ
Як і було сказано у вступі, дані алгоритми широко застосовуються в різних завданнях для пошуку найкоротшого шляху.
Алгоритм Дейкстри, а також його модифікації використовуються в області мереж, транспортних потоків, і звичайно ж в області обробки графів.
Наприклад протокол динамічної маршрутизації «OSPF» розбиває процес побудови таблиці маршрутизації на 2 етапи.
Другий етап полягає в знаходженні оптимальних маршрутів за допомогою створеного на першому етапі графа. На цьому етапі застосовується ітеративний алгоритм Дейкстри.Каждий маршрутизатор вважає себе центром мережі і шукає оптимальний маршрут до кожної відомої йому мережі.Ви кожному знайденому таким чином маршруті запам'ятовується тільки один крок-до наступного маршрутизатора, відповідно до принципу однокрокової маршрутізаціі.Данние про цей крок і потрапляють в таблицю маршрутізаціі.Еслі кілька маршрутів мають однакову метрику до мережі призначення, то в таблиці маршрутизації запам'ятовуються перші кроки всіх цих маршрутів.
Також алгоритм застосовується при евакуації населення з вогнищ лиха. Оптимальні маршрути до пунктів збору транспорту для кожної групи людей (будинок, вулиця, школа і т.п) в штабі МНС розраховує програма н...
