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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Нехай дано граф виду:

18

Потрібно знайти остове дерево мінімальної вартості даного орієнтованого графа за алгоритмом Флойда. Запустимо проект на виконання, після чого на екрані появиться форма виду:

26

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

« Попередня сторінка