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

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

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

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

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

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

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

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

Тоді, для того, щоб перейти від матриць Алгоритм Флойда і Алгоритм Флойда до матриць Алгоритм Флойдата Алгоритм Флойдавиконуємо наступні дії:

  1. Замінюємо значення комірки Алгоритм Флойда матриці Алгоритм Флойда на Алгоритм Флойда і у комірку Алгоритм Флойда матриці Алгоритм Флойда записуємо значення 1 (Алгоритм Флойда).
  2. Замінюємо значення комірки Алгоритм Флойда на Алгоритм Флойда і покладаємо Алгоритм Флойда.
  3. Замінюємо значення комірки Алгоритм Флойда на Алгоритм Флойда і покладаємо Алгоритм Флойд.
  4. Замінюємо значення комірки Алгоритм Флойда на Алгоритм Флойда і покладаємо Алгоритм Флойда.
  5. Замінюємо значення комірки Алгоритм Флойда на Алгоритм Флойда і покладаємо Алгоритм Флойда.

В результаті отримуємо матриці виду:

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

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

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

Після застосування трикутного оператора, до елементів виділених червоним кольором отримаємо:

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

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

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

В результаті отримуємо матриці:

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

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

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

Після виконання четвертого етапу отримуємо матриці:

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

Переходимо до останнього — 5-го етапу: покладаємо Алгоритм Флойда і робимо відповідні позначення в матрицях Алгоритм Флойда та Алгоритм Флойда.

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

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

Кінцеві матриці Алгоритм Флойда і Алгоритм Флойдамістять всю необхідну інформацію для визначення найкоротшого шляху між будь-якими двома вершинами графа. Наприклад, найкоротша відстань між вершинами 1 та 5 рівна Алгоритм Флойда.

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

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

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