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

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

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

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

Інтерфейс програми, яка здійснює пошук маршруту найкоротшої довжини за алгоритмом Дейкстри

Інтерфейс програми, яка здійснює пошук маршруту найкоротшої довжини за алгоритмом Дейкстри

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

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

Коментарі

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

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

    1) При розробці програми використана стандартна програмна реалізація, яка передбачає знаходження найкоротшого маршруту між початковою та кінцевою вершинам, більш доцільно знайти найкоротший маршрут між початковою та заданою вершиною. Чому це так важливо, уявіть у мене є орієнтований граф з 10 вершинами, в результаті виконання програми мені будуть запропоновані найкоротші маршрути від 1 до 2,3,...,10 вершини — це дуже ускладнює сприйняття отриманих результатів.

    2) Запропонована Вами довжина маршруту дорівнює сумі оптимальних маршрутів від початкової до проміжних вершин, це може ввести користувача в оману. Якби існувала можливість то найкоротші маршрути доцільно було б вивести в списках суміжності, наприклад:

    2: 1->2;

    3: 1->3;

    4: 1->2->3;

    -----------------

    10: 1->5->10

    Проте запропонована Вами реалізація є найкращою серед мені відомих. Я вдячний Вам за якісну роботу, за якісний контент.

  2. admin пише:

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

  3. andrey_khorolskiy пише:

    Дякую за оперативну та змістовну відповідь.

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