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

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

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

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

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

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

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

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

Етап k: на k-му кроці рядок і стовбець під номерок k, являються ведучим рядок і стовбцем. Для кожного елемента Алгоритм Флойда матриці Алгоритм Флойда, за умови, що виконується наступна нерівність:

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

виконуємо наступні дії:

  1. Створюємо матрицю Алгоритм Флойда, шляхом заміни в матриці Алгоритм Флойдаелемента Алгоритм Флойда наступною сумою Алгоритм Флойда.
  2. Створюємо матрицю Алгоритм Флойда, замінюючи в матриці Алгоритм Флойда елемент Алгоритм Флойда на k.

Розглянемо даний процес більш детально. Нехай на(k-1)-му кроці матрицяАлгоритм Флойдамає вигляд.

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

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

Після виконаня  n-го етапу алгоритму Флойда, найкоротший шлях між вузлями i та j з допомогою матриць Алгоритм Флойда і Алгоритм Флойда визначається наступним чином:

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

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар