2-й вершини дорівнює 7.
Аналогічну операцію проробляємо з двома іншими сусідами 1-й вершини - третій і 6-й.
Всі сусіди вершини 1 перевірені. Поточне мінімальна відстань до вершини 1 вважається остаточним і перегляду не підлягає. Викреслимо її з графа, щоб відзначити, що ця вершина переглянуло.
Крок №2. Знову знаходимо «найближчу» З не відвіданих вершин. Це вершина 2 з міткою 7.
Сусідами вершини 2 є 1, 3 і 4, перший по черзі - вже викреслена вершина 1, тому її в розгляд не беремо, друга за черзі - вершина 3, шлях до неї через вершину 2: 7 + 10=17, але 17 більше поточної мітки цієї вершини (9), тому мітка не змінюється. Також сусід другого вершини - вершина 4, відстань до неї через вершину 2: 7 + 15=22, 22 lt; , Присвоюємо вершині 4 мітку 22.
непереглянутих сусідів вершини 2 не залишилося, відстань до неї можна вважати остаточним, вершину помічаємо як відвідану.
Крок №3. Повторюємо крок алгоритму, вибравши вершину 3. Після перевірки всіх її сусідів отримуємо наступне:
Подальші кроки. Повторюємо крок алгоритму для залишилися вершин. Це будуть вершини 6, 4 і 5, відповідно до порядку.
Алгоритм завершує свою роботу коли всі вершини отримали постійну мітку. Результатом роботи алгоритму є найкоротша відстань від першої вершини до інших:
До другого - 7;
До третього - 9;
До четвертого - 20;
До п'ятого - 20;
До другого - 11.
. АЛГОРИТМ Беллмана-ФОРДА
Знаходить найкоротші шляхи від однієї вершини графа до всіх інших у зваженому графі. Вага ребер може бути негативним.
ЗАВДАННЯ
Дан орієнтований або неорієнтовані граф G зі зваженими ребрами. Потрібно знайти найкоротші шляхи від виділеної вершини s до всіх вершин графа.
АЛГОРИТМ
. Перед початком роботи алгоритму, для всіх вершин, крім стартової, відстань покладається рівним нескінченності.
. У циклі перевіряється необхідність виробляти релаксацію для конкретного ребра (порівняння поточного шляху, з заново порахувати).
. Якщо поточна мітка вершини більше ніж мітка нового шляху, то вона змінюється в його бік, інакше залишається незмінною.
. Алгоритм закінчує свою роботу, тільки якщо на одному з його чергових кроків не було проведено жодної релаксації.
ПРИКЛАД
Ініціалізація алгоритму. Мітка витоку прирівнюється 0, решта - нескінченності.
Крок № 1. У циклі проводиться перебір всіх ребер, починаємо з ребра 1-3. Для цього перевіримо чи не входить воно в шлях більш оптимальний, ніж вже знайдений. ? gt; 0 +6. Знайдений коротший шлях, мітка вершини 3 змінюється на значення 6 (проведена релаксація).
Крок №2. Перевіряємо ребро 2-1. Для цього перевіряємо - чи не є воно частиною більш короткого шляху, ніж вже знайдений. 0 lt ;? + 2.Релаксація не потрібна, мітка залишається незмінною.
Крок № 3. Перевіряємо ребро 3-2. Для цього перевіряємо - чи не є воно частиною більш короткого шляху, ніж вже знайдений. ? gt; 6 + 48.Найден коротший шлях, мітка вершини змінюється на значення 54 (проведена релаксація).
Крок 5-7. Знову перевіряємо ребра 1-3, 2-1, 3-2, в даному випадку релаксація не потрібно, мінімальні відстані вже знайдені.
Крок 8. Залишилося перевірити граф на наявність циклу негативного ваги, досяжного з стартової вершини. Для ребра 1-3 перевіряється - чи може воно ще поліпшити поточний знайдений шлях. Т.к. 1-3 не його не покращує, воно не входить в цикл негативного ваги.
Крок 9-10. Аналогічно ребру 1-3 перевіряються ребра 2-1 і 3-2.
У графі немає циклів негативного ваги, робота алгоритму закінчена.
. АЛГОРИТМ А *
Знаходить маршрут з найменшою вартістю від однієї вершини до іншої, використовуючи алгоритм пошуку по першому найкращому збігу на графі.
ЗАВДАННЯ
Дана матриця вузлів (двовимірний масив), кожен елемент масиву представляє вузол (клітку масиву), а його значенням є прохідність цієї клітини. Необхідно знайти шлях від стартової клітини до кінцевої, враховуючи непрохідність деяких клітин.
АЛГОРИТМ
Додаємо стартов...
