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

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

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

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

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

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

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

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

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

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

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

Знаходження найкоротшого шляху між двома вершинами в орієнтованому графі використовуючи алгоритм Дейкстри

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

Виходячи з того, що інтерфейс головної форми розглядуваного delphi-проекту аналогічний проектам, які реалізують інші алгоритми на графах, лише з однією відмінністю (панель інструментів міститься додаткове поле типу TEdit, в яке, способом введення з клавіатури, необхідно вказати номер вершини, для якої будується маршрут), то основні її елементи та процес побудови орієнтованого графа розглядати не будемо. Це все детально можна почитати перейшовши, наприклад, за посиланням Знаходження найкоротшого шляху від однієї вершини графа до всіх інших вершин в середовищі програмування delphi. А перейдемо до практики, тобто провіримо його роботу на конкретному прикладі.

Для цього, розглянемо деякий орієнтований граф, і припустимо, що для нього необхідно знайти мінімальний маршрут від вершини номер один, до вершини номер три.

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

Графічне представлення орієнтованого графа засобами Delphi

В параграфі Графічне представлення графа засобами Delphi ми створили проект, який малював неорієнтований граф на канві компонента Image1. Сьогодні розглянемо алгоритм побудови орієнтованого графа, тобто графа ребрам якого присвоєно певний напрямок. Послідовність дій при побудові вершин орієнтованого графа аналогічна послідовності дій, яку ми здійснювали у випадку неорієнтованого. Проте, процес побудови орієнтованого ребра дещо відрізняється. Для того, щоб нарисувати орієнтоване ребро, будемо використовувати наступний алгоритм: нехай маємо дві вершини графа (зображені у вигляді кола з центром у точках V1 та V2 і радіусом r). Для того, щоб побудувати ребро проведемо від точки V1 до V2 пряму лінію. Далі для того, щоб задати напрямок необхідно знайти точку перетину кола з центром в точці V2 та радіусом r з прямою, яка прорходить через дві точки V1 та V2. В результаті отримаємо деяку точку A. Далі, побудуємо деяке уявне коло з радіусом r1 (на малюнку зображено штрихпунктирною лінією), і знову знайдемо точку перетину даного кола з прямою V1V2. Отримуємо деяку точку B. Після того, як координати точки B відомі, виконуємо поворот даної точки відносно точки A, проти годинникової стрілки на кут l. В результаті отримуємо точку B1. Аналогічно, виконуємо поворот точки B за годинниковою стрілкою — отримуємо точку B2. Таким чином ми отримали трикутник AB1B2, який і буде вказувати напрямок орієнтованого ребра.

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

Знаходження найкоротшого маршруту для орієнтованого графі за алгоритмом Дейкстри в середовищі програмування Delphi(2)

Дана програма призначена для знаходження найкоротшого маршруту, за алгоритмом Дейкстри, від вершини №1 до всіх інших вершин орієнтованого графа, а також для підрахунку довжини даного маршруту.

Після запуску програми користувачу пропонується створити граф з допомогою кнопок панелі інструментів та області форми під назвою «Граф». Тобто для того, щоб намалювати вершини графа необхідно на панелі інструментів натиснути кнопку «Додати вершину» і з допомогою лівої кнопки миші розмістити її в області графічного представлення.

Створення вершин графа з допомогою delphi-програми «Алгоритм Дейкстри»

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

Знаходження найкоротшого маршруту для орієнтованого графі за алгоритмом Дейкстри в середовищі програмування Delphi(1)

Нехай потрібно визначити найкоротший маршрут в орієнтованому графі. Для цього будемо використовувати delphi-програму, яка будує необхідний маршрут, від вершини під номером один, до всіх інших вершин заданого графа і використовує для цього алгоритмом Дейкстри.

Після запуску програми необхідно вказати кількість вершин графа, для якого будемо шукати маршрут і натиснути кнопку «Створити матрицю». Тобто граф на екрані відображатиметься у вигляді матриці суміжності. Далі, необхідно заповнити її даними, які відповідатимуть за відстані між вершинами. Також відмітимо, що не існуючі ребра позначаються символом «-».

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

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

Приклад знаходження дерева мінімальної вартості для орієнтованого графа за алгоритмом Дейкстри

Розглянемо деякий орієнтований гряф, для якого потрібно знайти найкоротший маршрут від вершини 1 до всіх інших вершин. Для розв'язку задач такого типу доцільно використовувати алгоритм Дейкстри.

Алгоритм Дейкстри

Слідуючи алгоритму, початковій вершині (вершина під номером 1) присвоюємо постійну мітку Алгоритм Дейкстри після чого переходимо до першого етапу.

Етап 1: з вершини 1 існує орієнтоване ребро до вершин 2, 4 і 5. Обчислимо для даних вершин відповідні мітки. В результаті отримаємо наступну таблицю.

Алгоритм Дейкстри

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

Наступна сторінка »