Нехай дано деякий граф, для якого потрібно знайти дерево мінімальної вартості.
Для рішення даної проблеми використаємо алгоритм Флойда, з допомогою якого, за n етапів (n – кількість вершин графа), можна відшукати найкоротший маршрут між будь-якими двома вершинами графа.
Перш ніж приступити до розв’язку, запишемо початкову матрицю відстаней та початкову матрицю вершин
.
Переходимо до 1-го етапу: в матриці виділимо синім кольором ведучий рядок і колонку під номером
. Також, червоним кольором виділимо ті елементи матриці
, значення яких можна покращити з допомогою трикутного оператора.
Тоді, для того, щоб перейти від матриць і
до матриць
та
виконуємо наступні дії:
- Замінюємо значення комірки
матриці
на
і у комірку
матриці
записуємо значення 1 (
).
- Замінюємо значення комірки
на
і покладаємо
.
- Замінюємо значення комірки
на
і покладаємо
.
- Замінюємо значення комірки
на
і покладаємо
.
- Замінюємо значення комірки
на
і покладаємо
.
В результаті отримуємо матриці виду:
Переходимо до 2-го етапу: покладаємо . Виділимо в матриці
ведучий рядок і колонку синім кольором, а також, позначимо червоним кольором елементи, до яких будемо застосовувати трикутний оператора Флойда.
Після застосування трикутного оператора, до елементів виділених червоним кольором отримаємо:
Переходимо до 3-го етапу: покладаємо , в матриці
позначемо ведучі рядок та колонку і застосуємо трикутний оператор до елементів матриць
і
виділених червоним кольором.
В результаті отримуємо матриці:
4-й етап: покладаємо , в матриці
позначемо ведучі рядок і колонку а також в матрицях
та
виділимо елементи, які підлягають критерію покращення за алгоритмом Флойда.
Після виконання четвертого етапу отримуємо матриці:
Переходимо до останнього – 5-го етапу: покладаємо і робимо відповідні позначення в матрицях
та
.
Ніяких дій на даному етапі не виконуємо, бо матриця не містить елементів, які можна покращити застосувавши трикутний оператор. На цьому алгоритм Флойда закінчується.
Кінцеві матриці і
містять всю необхідну інформацію для визначення найкоротшого шляху між будь-якими двома вершинами графа. Наприклад, найкоротша відстань між вершинами 1 та 5 рівна
.
Для визначення відповідних маршрутів виходимо з наступних міркувань: маршрут від вершини i до вершини j поєднаний ребром (i, j) тоді і тільки тоді, коли . В іншому випадку вершини i та j поєднані, принаймі, через одне проміжне ребро. Тобто, якщо
а
, то найкоротшим маршрутом між вершинами 1 і 5 буде маршрут виду
.