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

Дана програма призначена для знаходження найкоротшого маршруту, за алгоритмом Дейкстри, від вершини №1 до всіх інших вершин орієнтованого графа, а також для підрахунку довжини даного маршруту.

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

Створення вершин графа з допомогою програми Алгоритм Дейкстри

Створення вершин графа з допомогою програми Алгоритм Дейкстри

Читати повністю

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

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

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

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

Читати повністю

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

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

Позначемо через Алгоритм Дейкстри найкоротша відстань від початкової вершини 1 до вершини i, через Алгоритм Дейкстри — довжину ребра (i, j). Тоді для вершини j мітка Алгоритм Дейкстри визначається наступним чином:

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

Мітки в алгоритмі Дейкстри можуть бути двох типів: тимчасові або постійні. Тимчасова мітка може бути замінена на нову також тимчасову, якщо в процесі виконання алгоритму буде знайдено більш короткий маршрут до даної вершини. Якщо ж в процесі виконання алгоритму виявиться, що  більш короткого маршруту від початкової до даної вершини не існує, то змінюємо статус тимчасової мітки на постійну.

Читати повністю

Визначення найкоротшого шляху за алгоритмом Флойда

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

Алгоритм Флойда

Трикутний оператор Флойда

Якщо виконується нерівність Алгоритм Флойда, то доцільно замінити маршрут від вершини i до  вершини k (Алгоритм Флойда) маршрутом Алгоритм Флойда. Така заміна (іншими словами трикутний оператор) виконується в процесі виконання алгоритму Флойда.

Алгоритм Флойда складається з n етапів (де n кількість вершин графа).

Етап 0: на даному етапі визначаємо початкову матрицю відстаней Алгоритм Флойда і матрицю послідовності вершин Алгоритм Флойда. Діагональні елементи обох матриць в обчисленні не беруть участь, тому позначаємо їх символом «-». Також на даному етапі покладають Алгоритм Флойда.

Читати повністю

Алгоритм Крускала

Алгоритм Крускала, так само, як і алгоритм Прима призначений для пошуку дерева мінімальної вартості неорієнтованого графа. Основна відмінність між даними алгоритмами полягає в тому, що пошук дерева мінімальної довжини за алгоритмом Крускала починається з n дерев, кожне з яких складається з однієї вершин. І на кожному кроці виконуємо операцію об'єднання двох дерев, використовуючи для цього ребро найкоротшої довжини. Процес продовжується поки не отримаємо єдине дерево, яке охоплює всі n вершин вхідного графа, і не містить циклів.

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

Алгоритм Крускала

Крок 1: вибираємо ребро найменшої вартості: 1−3=1. В результаті отримаємо одне дерево, яке складається з двох вершин і одного ребра (на малюнку позначено зеленим кольором) та 4 дерева, які містять по одній вершині.

Читати повністю

Знаходження дерева мінімальної вартості за алгоритмом Крускала на Delphi(2)

Програма знаходить дерево мінімальної вартості неорієнтованого графа використовуючи алгоритм Крускала. Побудова графа здійснюється у візуальному редакторі та з допомогою матриці суміжності.

Головна форма даного проекту аналогічна формі програми, яка реалізує алгоритм Прима, тому більш детально переглянути процес побудови графа та знаходження дерева мінімальної вартості можна перейшовши за посиланням алгоритм Прима на Delphi(2).

Алгоритм Крускала на Delphi

Читати повністю

Знаходження дерева мінімальної вартості за алгоритмом Прима на Delphi(1)

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

14

Запустимо проект на виконання, в результаті на екрані монітора появиться форма наступного виду:

Читати повністю