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

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

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

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

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

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

Створення вершин графа

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

Створивши вершини, переходимо до встановлення з’єднань між відповідними парами вершин графа. Зазначимо, що реалізується це двома способами: за допомогою матриці суміжноісті та за допомогою кнопок панелі задач. Перший спосіб полягає у заповненні комірок таблиці TStringGrid значеннями, які і відповідатимуть за відстані між вершинами. І процедура другого способу аналогічна розглянутій вище процедурі створення та видалення вершин графа.

Побудова орієнтованого ребра

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

Побудова дерева найкоротших шляхів

Скачати delphi-проект алгоритм Беллмана-Форда.

12 коментарів

  1. Дякую за розміщений матеріал. Все як завжди цікаве, потрібне, якісне. Раджу колегам.

  2. Дякую за розміщений матеріал, проте є декілька зауважень.
    По-перше, можливо, ця проблема виникає лише у мене, але при вершин на робочій області виникає помилка “invalid pointing value…”
    По-друге, як я зрозумів, відстань можна задавати лише через команду “додати ребро”. Через заповнення матриці суміжності неможливо (навідміну від реалізації алгоритму Дейкстри)
    По-третє, зазвичай алгоритм Беллмана-Форда працює як від першої вершини від останьої, так можна задаати відстані і від останьої до першої – так званий “зворотня прогонка”.
    Буду вдячним за відповідь. Якщо зацікавить, то можу більш детально описати проблему та надати скріни.
    З повагою, А.О. Хорольський

  3. Доброго вечора Андрій. Не зовсім зрозумілим являється третє зауваження. Якщо можна, то опишіть його більш детально.

  4. Це питання відноситься до більш практичної реалізації. Наприклад, якщо стоїть задача мінімізувати собівартість видобутку та ін. То зазвичай, починають з “кінця” коли вже відомі обєми виробництва. Наприклад в стандартній постановці обудуємо мережеву модель із 12 вершин. При цьому ребра будемо задавати від 1 до 2 вершини, від 2 до 5 та ін. А найкоротший маршрут будемо шукати від вершини 1 до вершини 12.
    А при “зворотному прогоні” будуємо мережеву модель та направляємо ребра із вершини 12 до вершини 10 та ін. Тобто будемо зєднувати не вершину 1 з 2, а 2 з 1.
    Якщо буде необхідність, то можу більш детально описати виходячи із “першоджерел”.
    З повагою, А.О. Хорольський

  5. На скільки я зрозумів, Вам потрібно, щоб всі ребра заданого графа мінялись на протилежні, і алгоритм Беллмана-Форда виконувався для отриманого таким чином графа.

  6. Зрозуміло. Будемо пробувати реалізувати це.

  7. Дякую. За Ваші старання. Чи можна якимось чином підтримати Ваш сайт (в матеріальному плані)?

  8. Доброго дня Андрій. Delphi-програма, що реалізує алгоритм Беллмана-Форда згідно з Вашими поправками міститься за посиланням нижче. Для того, щоб побудувати дерево найкоротших шляхів для орієнтованого графа, ребра якого являються протилежними до заданого, на першому кроці, необхідно активізувати перемикач «Побудувати обернений граф», після чого, скористатись кнопкою «Знайти дерево мінімальної вартості».
    Алгоритм Беллмана-Форда на delphi
    Скачати delphi-проект Побудова дерева мінімальної вартості використовуючи алгоритм Беллмана-Форда.

  9. Дякую. Все чудово. Проте виникає ще одне питання, чи є можливість знаходження маршруту від 1 до 2, від 1 до 3, від 1 до 4 та ін. А не від 1 до кінцевої?
    За аналогією з алгоритмом Дейкстри?
    Де дані виводились в Memo.
    Довжина найкоротшого маршруту до точки 2: …
    Довжина найкоротшого маршруту до точки 3: …
    Довжина найкоротшого маршруту до точки 7: 1->2->5->7: …
    А також це не саме важливе, змінити значення з integer на real?
    Буду вдячним за відповідь.
    Всього найкращого Вам і Вашому чудовому сайту. Буду рекомендувати колегам.

  10. Дякую. Всього найкращого Вам та вашому сайту. Буду радити колегам.

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

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

*