Розв’язок задачі про найкоротший шлях використовуючи алгоритм Беллмана-Форда

Алгоритм Беллмана-Форда – це алгоритм, який обчислює найкоротші шляхи від однієї вихідної вершини до всіх інших вершин в зваженому орієнтованому графі. Безумовно, він являється повільнішим, ніж алгоритм Дейкстри для тієї ж задачі, але більш універсальний, оскільки здатний обробляти графи, в яких вага деяких ребер приймає від’ємного значення. Алгоритм зазвичай називають на честь двох його розробників, Річарда Беллмана і Лестера Форда, які опублікували його у 1958 та 1956 роках відповідно. Тим не менш, Едвард Форест Мур також опублікував даний алгоритм у 1957 році, і з цієї причини його також іноді називають алгоритмом Беллмана-Форда-Мура.

Алгоритм Беллмана-Форда

Різниця в кінцеваому результаті між алгоритмом Беллмана-Форда та алгоритмом Дейкстри

Як уже зазначалося вище, алгоритм Беллмана-Форда підходить для роботи з графами, що мають ребра з від’ємною вагою. Однак, якщо граф містить «від’ємний цикл», тобто цикл, сума ваги ребер якого дорівнює від’ємному значенню, тоді, для даного графа, не існує дерева найкоротших шляхів (будь-який шлях такого типу може бути покращений ще одним проходом через ребра, що утворюють від’ємний цикл). В такому випадку алгоритм Беллмана-Форда може виявити цикли від’ємної довжини і повідомити про їх існування, але він не може дати правильну відповідь, тобто знайти найкоротший шлях, якщо від’ємний цикл досяжний з вершини джерела.

Запишемо алгоритм Беллмана-Форда більш детально. Для цього, розглянемо деякий орієнтований граф  із зваженими ребрами, який не містить циклів від’ємної довжини. І припустимо, що потрібно знайти найкоротші шляхи від виділеної вершини до всіх інших вершин даного графа:

  1. Перед початком виконання алгорітму всі вершини графа вважаються непройденими, а ребра – не переглянутими. Кожній вершині в ході виконання алгоритму присвоюється число , рівне довжині найкоротшого шляху з вершини  у вершину , що включає тільки пройдені вершини. На першому кроці покладаємо  і для всіх , відмінних від . Також, на даному кроці, вершині  присвоюється мітка «пройдена» і покладається  ( – остання з пройдених вершин).
  2. Для кожної з вершин графа  наступним чином перерахувати величину  (де – вага ребра ). Якщо  для всіх непройдених вершин , процедуру алгоритму Беллмана-Форда необхідно завершити (у вихідному графі відсутні шляхи з вершини  у непройдені вершини). В іншому випадку, мітку «пройдена» необхідно присвоїти тій з вершин , для якої величина  є найменшою. Крім того, ребро, що веде в обрану на даному етапі вершину  вважається переглянутим (для цієї дуги досягався мінімум відповідно до виразу (1)). Після цього, поклавши , ітераційний процес продовжується далі. Відмітимо, що якщо для деякої пройденої вершини  відбувається зменшення величини , то з цієї вершини і инцидентного їй переглянутого ребра відповідні  мітки знімаються.
  3. Процедура алгоритму Беллмана-Форда завершується тільки тоді, коли всі вершини графа  пройдені і коли після чергового виконання кроку номер два жодне з чисел  не змінило свого значення.

Алгоритм Беллмана-Форда – приклад:

Використовуючи алгоритм Беллмана-Форда, побудувати дерево найкоротших шляхів для орієнтованого графа зображеного на наступному рисунку.

Алгоритм Беллмана-Форда приклад

Орієнтований граф що містить ребра від’ємної довжини

Згідно з розглянутим алгоритмом, на першому кроці, мітку «пройдена» присвоїмо вершині номер один і припустимо, що . Після цього, поклавши та скориставшись формулою (1), здійснюємо перерахунок величин :

Оскільки значення довжини  менше за , мітка «пройдена» присвоюється вершині «2». Разом з нею, переглянутим вважається також і ребро , з якого і складається поточне дерево найкоротших шляхів.

Виходячи з того, що переглягуті не всі вершини заданого графа, робимо перехід до кроку номер два, а саме покладаємо і виконуємо перерахунок величин :

Переглянувши отримані результати бачимо, що довжина , на даному етапі, приймає найменшого значення, тому, вершині «5» присвоюємо мітку «пройдена», а ребру – «переглянуте» (на даному етапі дерево найкоротших шляхів складається з ребер  та ).

Далі, покладаємо і знову-таки виконуємо перерахунок величин :

Після цього, доповнюємо шукане дерево ребром (вершина «4» і ребро  вважаються пройденою та переглянутими відповідно) і, виходячи з того, що серед вершин заданого графа не всі являються пройденими, покладаємо , після чого, продовжуємо алгоритм Беллмана-Форда далі:

З отриманих результатів бачимо, що на даному етапі мітку «пройдена» необхідно присвоїти вершині номер «3» та мітку «переглянуте» – ребру .

Виходячи з того, що всі вершини графа вважаються пройденими, покладаємо і, з метою спробувати зменшити числа , здійснюємо повернення до кроку номер два:

Оскільки мітку «пройдена» присвоїно всім вершинам графа і на попередньому кроці алгоритму жодну з величин  не вдалося зменшити, процедура алгоритму Беллмана-Форда завершується.

Алгоритм Беллмана-Форда приклад

Дерево найкоротших шляхів

Таким чином, дерево найкоротших шляхів, для заданого орієнтованого графа, складається з наступних ребер:  (ребра, які, після виконання алгоритму, були помічені як переглянуті).

Блок-схема алгоритму Беллмана-Форда

Алгоритм Беллмана-Форда блок-схема

Залишити коментар

Your email address will not be published. Required fields are marked *

*