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

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

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

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

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

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

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

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

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

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

18

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

26

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

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