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

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

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

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

algoritm_dejkstru_delphi35
Орієнтований граф, для якого відшукується мінімальний маршрут

Отже, запустивши проект на виконання, з допомогою графічного редактора побудуємо його вершини та поєднаємо їх відповідними орієнтованими ребрами. В результаті виконання даного кроку, головна форма прийме наступний вигляд:

Алгоритм Дейкстри на delphi
Побудова вершин заданого графа та поєднання їх відповідними орієнтованими ребрами

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

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

Скачати delphi-проект Знаходження найкоротшого шляху між двома вершинами в орієнтованому графі використовуючи алгоритм Дейкстри.

Ми в соціальних мережах

Один коментар

  1. Доброго дня! Дякую за дуже вдалу реалізацію алгоритму Дейкстри. З усіх розглянутих і відомих це найкраща реалізація алгоритму Дейкстри.

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

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

*