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

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

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

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

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

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

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

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

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

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

Скачати delphi-проект алгоритм Дейкстри.

5 коментарів

  1. Дякую за розроблену досить вдалу реалізацію алгоритму. Бажано передбачити можливість пошуку найкоротшого маршруту не тільки між початковою та кінцевою вершинами, але і між початковою і проміжною без пошуку маршруту до кінцевої. При вирішенні задач оптимізації виробничих процесів існує потреба знаходити проміжні маршрути, в іншому випадку спостерігається “нагромаджування” робочої області. Хоча, зважаючи на класичну реалізацію алгоритму програма зроблена вірно – пошук завершується коли всі вершини і дуги помічені.

  2. Немає за що Андрій. Ми дуже раді, що даний матеріал став для Вас корисним. А що стосується побажання, то найближчим часом воно буде реалізовано.

  3. Дякую за гарну реалізацію алгоритму. Незважаючи на всі переваги є декілька питань, які необхідно розкрити:
    1) довжина між вершинами задається цілим числом, чи є можливість реалізації, якщо довжина маршруту задається дробовим числом?
    2)чи є можливість окремо виводити значення найкоротших маршрутів, тобто від 1 до 2, від 1 до 3 та ін. при цьому значення довжини маршруту окремо виводиться від 1 до 2, від 1 до 3 та ін.; (у Вашому випадку довжина визначається для усіх найкоротших маршрутів – (1-4)=30+(4-5)=20, виходить 30+20=50, а не 120.
    Якщо є можливість, то дайте роз’яснення.
    З повагою та вдячністю, А.О. Хорольський

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

    алгоритм Дейкстри на delphi

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

  5. Дякую за відповідь. Питань не маю.

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

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

*