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

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

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

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

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

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

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

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

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

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

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

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

Коментарі

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

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

  2. admin пише:

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

  3. khorolskiy_andrey пише:

    Дякую за гарну реалізацію алгоритму. Незважаючи на всі переваги є декілька питань, які необхідно розкрити:

    1) довжина між вершинами задається цілим числом, чи є можливість реалізації, якщо довжина маршруту задається дробовим числом?

    2)чи є можливість окремо виводити значення найкоротших маршрутів, тобто від 1 до 2, від 1 до 3 та ін. при цьому значення довжини маршруту окремо виводиться від 1 до 2, від 1 до 3 та ін.; (у Вашому випадку довжина визначається для усіх найкоротших маршрутів — (1−4)=30+(4−5)=20, виходить 30+20=50, а не 120.

    Якщо є можливість, то дайте роз'яснення.

    З повагою та вдячністю, А.О. Хорольський

  4. admin пише:

    Доброго вечора Андрій.

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

    В даному проекті також передбачено ввід не тільки цілих чисел а і чисел з плавачою комою. А що стосується дробових чисел, то опишіть будь ласка більш детально, що Ви маєте на увазі. В якому форматі вони повинні задаватись.

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

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

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

  5. khorolskiy_andrey пише:

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

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