Алгоритм Форда-Беллмана (реалізація в середовищі Delphi)

У математиці та інформатиці існує окремий розділ, який називається теорія графів. Основним предметом вивчення даного розділу є математичний об'єкт, який називається графом (об'єкт, який представляє собою множину вершин і набір ребер, які виступають в якості з'єднань між парами вершин). В рамках даного розділу ставляться і вирішуються різні задачі пов'язані з цим об'єктом. Найпоширенішшою серед них є задача про знаходження найкоротшого шляху між будь-якими двома вершинами графа. Зазначимо, що одним з найбільш використовуваних методів рішення задач такого типу являється метод Дейкстри.

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

Головне вікно проекту "Знаходження дерева мінімальної вартості за алгоритмом Беллмана-Форда"

Отже, головна форма розглядуваного проекту складається з панелі інструментів (містить кнопки «Додати вершину», «Видалити вершину», «Додати ребро», «Видалити ребро», «Видалити граф» і «Знайти дерево мінімальної вартості»), області графічного представлення, області представлення графа у вигляді матриці та області виводу результатів (компонент типу TStatusBar, призначений для виводу розв'язку у вигляді списку ребер).

Читати повністю

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

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

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

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

Читати повністю

Пошук Гамільтоновго циклу в неорієнтованому графі

Гамільтоновим циклом (Гамільтоновим ланцюгом) неорієнтованого графа називають простий цикл, що містить всі його вершини в точності по одному разу. Зовні визначення Гамільтонового циклу схоже на визначення Ейлерового циклу. Однак є кардинальна відмінність в складності розв'язку відповідних задач на розпізнавання і побудову. Тобто, якщо при розгляді Ейлерового циклу ми бачили, що для нього існує досить простий критерій перевірки його існування і ефективний алгоритм його побудови. То для Гамільтонових же циклів невідомо ніяких необхідних і достатніх умов їх існування, а всі відомі алгоритми вимагають, для деяких графів, перебору великого числа варіантів.

Читати повністю