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

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

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

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

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

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

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

3 коментаря

  1. Дякую за гарну реалізацію алгоритму, проте є декілька побажань:
    1) При розробці програми використана стандартна програмна реалізація, яка передбачає знаходження найкоротшого маршруту між початковою та кінцевою вершинам, більш доцільно знайти найкоротший маршрут між початковою та заданою вершиною. Чому це так важливо, уявіть у мене є орієнтований граф з 10 вершинами, в результаті виконання програми мені будуть запропоновані найкоротші маршрути від 1 до 2,3,..,10 вершини – це дуже ускладнює сприйняття отриманих результатів.
    2) Запропонована Вами довжина маршруту дорівнює сумі оптимальних маршрутів від початкової до проміжних вершин, це може ввести користувача в оману. Якби існувала можливість то найкоротші маршрути доцільно було б вивести в списках суміжності, наприклад:
    2: 1->2;
    3: 1->3;
    4: 1->2->3;
    —————–
    10: 1->5->10
    Проте запропонована Вами реалізація є найкращою серед мені відомих. Я вдячний Вам за якісну роботу, за якісний контент.

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

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

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

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

*