Приклад знаходження дерева мінімальної вартості для орієнтованого графа за алгоритмом Флойда
Нехай дано деякий граф, для якого потрібно знайти дерево мінімальної вартості.
Для рішення даної проблеми використаємо алгоритм Флойда, з допомогою якого, за n етапів (n — кількість вершин графа), можна відшукати найкоротший маршрут між будь-якими двома вершинами графа.
Перш ніж приступити до розв'язку, запишемо початкову матрицю відстаней та початкову матрицю вершин
.
Переходимо до 1-го етапу: в матриці виділимо синім кольором ведучий рядок і колонку під номером
. Також, червоним кольором виділимо ті елементи матриці
, значення яких можна покращити з допомогою трикутного оператора.