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

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

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

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

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

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

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

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

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

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

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

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

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

Коментарі

4 коментаря по темі “Знаходження найкоротших маршрутів від першої до всіх інших вершин в орієнтованому графі”
  1. khorolskiy_andrey пише:

    Доброго дня!

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

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

    2) Доречно було б, додати кнопку «Заповнити пусті комірки», або при побудові матриці одразу виводити заповнену матрицю. Уявіть, якщо кількість вершин 8, то слід заповнити 64 комірки, а коли 9 вже 81!!! Звісно дане питання не принципове, однак хотілось би мати уявлення.

    3) Також слід додати «перехоплення помилок», тобто вивід повідомлення, якщо не всі комірки заповнені.

    4) Можливо, більш доречно задати фіксований розмір робочого вікна після видалення матриці, а не встановлювати рівним панелі.

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

  2. admin пише:

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

  3. admin пише:

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

    Delphi-проект, що описується в даному параграфі було відредаговано згідно з вказаними вище пунктами.

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

  4. khorolskiy_andrey пише:

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

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