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

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

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

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

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

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

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

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

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

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

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

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

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

Матеріал був корисним, поділись в соціальних мережах:

Коментарі

Один коментар по темі “Алгоритм Форда-Беллмана (реалізація в середовищі Delphi)”
  1. khorolskiy_andrey пише:

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

Якщо тобі сподобалась дана тема, залиш свій коментар