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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ми в соціальних мережах

• 
• 
• 
•