Алгоритм Шімбелла (реалізація в середовищі Delphi)

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

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

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

schimbels_method_delphi1

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

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

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

Створення орієнтованого ребра

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

schimbels_method_delphi3

Знаходження найкоротших шляхів за допомогою delphi-програми «Метод Шімбелла»

Зауваження: кожен з найкоротших шляхів в області графічного представлення можна переглянути перемістивши курсор миші на відповідний рядок компонента TMemo.

Скачати delphi-проект метод Шімбелла.

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