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

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

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

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

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

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

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

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

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

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

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

7 коментарів

  1. Доброго дня!
    Дякую за вдалу реалізацію алгоритму Дейкстри. Незважаючи на всі переваги є декілька уточнень, які слід відобразити в описі:
    1) В разі, якщо маршрут між вершинами відсутній, то в якості значення слід ввести «- .», на це треба звернути увагу і вказати при описі, тому що деякі реалізації передбачають в якості розділювача використовувати «0». На це слід звернути увагу. Дана правка буде доцільною, особливо для тих хто не має навичок програмування.
    2) Доречно було б, додати кнопку «Заповнити пусті комірки», або при побудові матриці одразу виводити заповнену матрицю. Уявіть, якщо кількість вершин 8, то слід заповнити 64 комірки, а коли 9 вже 81!!! Звісно дане питання не принципове, однак хотілось би мати уявлення.
    3) Також слід додати «перехоплення помилок», тобто вивід повідомлення, якщо не всі комірки заповнені.
    4) Можливо, більш доречно задати фіксований розмір робочого вікна після видалення матриці, а не встановлювати рівним панелі.
    Всі ці зауваження не є принциповими. Навіть не зауваження, а уточнення і побажання, які дозволять уникнути непорозумінь у користувачів.

  2. Доброго дня Андрій. Завжди приємно читати Ваші коментарі щодо розроблених нами delphi-проектів. А що стосується уточнень та побажань, то найближчим часом вони будуть реалізовані.

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

  4. Дякую! питань більше не маю. Ви найкращий сайт, а Ваше відношення до користувачів заслуговує поваги.

  5. Досить гарна реалізація. Цікаво побачити реалізацію алгоритму Беллмана-Форда.

  6. Доброго вечора Андрій.
    Ми дуже раді, що Ви в черговий раз виявляєте інтерес до розроблених нами Delphi-проектів.
    Найближчим часом, розділ Дослідження операцій, сайту mathros.net.ua, буде доповнено теоретичною частиною алгоритму, основним призначенням якого є пошук найкоротшого шляху в зваженому графі, використовуючи метод Беллмана-Форда та у розділі Програми на Delphi (Дослідження операцій) буде розміщено Delphi-програму, що реалізує даний алгоритм.

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

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

*