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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Коментарі

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

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

  2. admin пише:

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

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