Знаходження найкоротших маршрутів від першої до всіх інших вершин в орієнтованому графі

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

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

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

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

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

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

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

Представлення графа у вигляді матриці суміжності

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

Знаходження найкоротших маршрутів від першої до всіх інших вершин в орієнтованому графі

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

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

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