Дана програма призначена для знаходження найкоротшого маршруту, за алгоритмом Дейкстри, від вершини №1 до всіх інших вершин орієнтованого графа, а також для підрахунку довжини даного маршруту.
Після запуску програми користувачу пропонується створити граф з допомогою кнопок панелі інструментів та області форми під назвою «Граф». Тобто для того, щоб намалювати вершини графа необхідно на панелі інструментів натиснути кнопку «Додати вершину» і з допомогою лівої кнопки миші розмістити її в області графічного представлення.
Також в даній програмі передбачено можливість переміщення вершини, яке здійснюється наступним чином: натиснути лівою кнопкою мишки по вершині графа після чого перетягнути її в потрібне місце (переміщення вершин можливе лише в тому випадку, коли на панелі задач активована кнопка «Додати вершину»). Для видалення вершини необхідно активувати відповідну кнопку на панелі задач і натиснувши лівою кнопкою мишки по ній.
Після того, як вершини створено потрібно пов’язати їх орієнтованими ребрами. Орієнтоване ребро в даній програмі можна створювати і видаляти двома способами: з допомогою матриці суміжноісті та з допомогою кнопок панелі задач. Перший спосіб полягає в тому, що ми заповнюємо матрицю суміжності (міститься в області форми під назвою «Матриця суміжності») значеннями, які і відповідатимуть за відстані між вершинами. Процедура другого способу аналогічна вище розглянутій процедурі створення і видалення вершин графа.
Далі, для того, щоб побудувати найкоротший маршрут потрібно скористатись кнопкою «Знайти дерево мінімальної вартості», після натискання якої ребра, які формують мінімальний маршрут підсвічуються зеленим кольором і довжина даного маршруту виводиться в статусному рядку форми.
Скачати delphi-проект алгоритм Дейкстри.
Дякую за розроблену досить вдалу реалізацію алгоритму. Бажано передбачити можливість пошуку найкоротшого маршруту не тільки між початковою та кінцевою вершинами, але і між початковою і проміжною без пошуку маршруту до кінцевої. При вирішенні задач оптимізації виробничих процесів існує потреба знаходити проміжні маршрути, в іншому випадку спостерігається “нагромаджування” робочої області. Хоча, зважаючи на класичну реалізацію алгоритму програма зроблена вірно – пошук завершується коли всі вершини і дуги помічені.
Немає за що Андрій. Ми дуже раді, що даний матеріал став для Вас корисним. А що стосується побажання, то найближчим часом воно буде реалізовано.
Дякую за гарну реалізацію алгоритму. Незважаючи на всі переваги є декілька питань, які необхідно розкрити:
1) довжина між вершинами задається цілим числом, чи є можливість реалізації, якщо довжина маршруту задається дробовим числом?
2)чи є можливість окремо виводити значення найкоротших маршрутів, тобто від 1 до 2, від 1 до 3 та ін. при цьому значення довжини маршруту окремо виводиться від 1 до 2, від 1 до 3 та ін.; (у Вашому випадку довжина визначається для усіх найкоротших маршрутів – (1-4)=30+(4-5)=20, виходить 30+20=50, а не 120.
Якщо є можливість, то дайте роз’яснення.
З повагою та вдячністю, А.О. Хорольський
Доброго вечора Андрій.
Розроблений в даному параграфі delphi-проект призначений для побудови дерева найкоротших шляхів в орієнтованому графі використовуючи алгоритм Дейкстри. І результуюча довжина виводиться як сума довжини кожного з ребер даного дерева. Якщо є необхідність виводити мінімальний маршрут від початкової виршини (в нашому випадку це вершина під номером 1), до решти вершин заданого графа, то це дуже легко вирішується. За наступним посиланням міститься delphi-проект, який реалізує дане побажання.
В даному проекті також передбачено ввід не тільки цілих чисел і чисел з плавачою комою. А що стосується дробових чисел, то опишіть будь ласка більш детально, що Ви маєте на увазі. В якому форматі вони повинні задаватись.
Знаходження найкоротшого маршруту для орієнтованого графі за алгоритмом Дейкстри .
До речі, переглянути кожен з мінімальних маршрутів в області графічного представлення можна перемістивши курсор миші на відповідний рядок компонента виводу результатів TMemo.
Дякую за відповідь. Питань не маю.