В чем разница между алгоритмом Уоршелла и обычным перемножением матриц при построении матрицы достижимости?

Разница между алгоритмом Уоршелла и обычным перемножением матриц при построении матрицы достижимости заключается в скорости выполнения.

Обычное перемножение матриц предполагает пошаговое перемножение матриц с последующим сложением результатов каждого шага. ru.wikipedia.org ru.ruwiki.ru Получившаяся матрица будет состоять не только из 0 и 1, но и характеризовать количество путей между вершинами. ru.wikipedia.org ru.ruwiki.ru

Алгоритм Уоршелла позволяет найти матрицу достижимости в точности за определённое количество шагов, а именно за 2n^3. ru.wikipedia.org ru.ruwiki.ru

Таким образом, алгоритм Уоршелла обеспечивает более быстрое выполнение процесса, чем обычное перемножение матриц.