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

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

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

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

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

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

Delphi-проект розроблено за проханням користувача на ім'я andrey_khorolskiy («...Бажано передбачити можливість пошуку найкоротшого маршруту не тільки між початковою та кінцевою вершинами, але і між початковою і проміжною без пошуку маршруту до кінцевої...») і реалізує процес знаходження найкоротшого шляху між двома вершинами в орієнтованому графі, використовуючи для цього алгоритм Дейкстри.

Виходячи з того, що інтерфейс головної форми розглядуваного delphi-проекту аналогічний проектам, які реалізують інші алгоритми на графах, лише з однією відмінністю (панель інструментів міститься додаткове поле типу TEdit, в яке, способом введення з клавіатури, необхідно вказати номер вершини, для якої будується маршрут), то основні її елементи та процес побудови орієнтованого графа розглядати не будемо. Це все детально можна почитати перейшовши, наприклад, за посиланням Знаходження найкоротшого шляху від однієї вершини графа до всіх інших вершин в середовищі програмування delphi. А перейдемо до практики, тобто провіримо його роботу на конкретному прикладі.

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

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

Графічне представлення орієнтованого графа засобами Delphi

В параграфі Графічне представлення графа засобами Delphi ми створили проект, який малював неорієнтований граф на канві компонента Image1. Сьогодні розглянемо алгоритм побудови орієнтованого графа, тобто графа ребрам якого присвоєно певний напрямок. Послідовність дій при побудові вершин орієнтованого графа аналогічна послідовності дій, яку ми здійснювали у випадку неорієнтованого. Проте, процес побудови орієнтованого ребра дещо відрізняється. Для того, щоб нарисувати орієнтоване ребро, будемо використовувати наступний алгоритм: нехай маємо дві вершини графа (зображені у вигляді кола з центром у точках V1 та V2 і радіусом r). Для того, щоб побудувати ребро проведемо від точки V1 до V2 пряму лінію. Далі для того, щоб задати напрямок необхідно знайти точку перетину кола з центром в точці V2 та радіусом r з прямою, яка прорходить через дві точки V1 та V2. В результаті отримаємо деяку точку A. Далі, побудуємо деяке уявне коло з радіусом r1 (на малюнку зображено штрихпунктирною лінією), і знову знайдемо точку перетину даного кола з прямою V1V2. Отримуємо деяку точку B. Після того, як координати точки B відомі, виконуємо поворот даної точки відносно точки A, проти годинникової стрілки на кут l. В результаті отримуємо точку B1. Аналогічно, виконуємо поворот точки B за годинниковою стрілкою — отримуємо точку B2. Таким чином ми отримали трикутник AB1B2, який і буде вказувати напрямок орієнтованого ребра.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приклад знаходження дерева мінімальної вартості для орієнтованого графа за алгоритмом Флойда

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

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

Для рішення даної проблеми використаємо алгоритм Флойда, з допомогою якого, за n етапів (n — кількість вершин графа),  можна відшукати найкоротший маршрут між будь-якими двома вершинами графа.

Перш ніж приступити до розв'язку, запишемо початкову матрицю відстаней Алгоритм Флойда та початкову матрицю вершин Алгоритм Флойда.

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

Переходимо до 1-го  етапу: в матриці Алгоритм Флойда виділимо синім кольором ведучий рядок і колонку під номеромАлгоритм Флойда. Також, червоним кольором виділимо ті елементи матриці Алгоритм Флойда, значення яких можна покращити з допомогою трикутного оператора.

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

Наступна сторінка »