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

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

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

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

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

Читати повністю