40. Алгоритм вычисления расстояний между всеми парами вершин графа. Общий случай.

Очевидно, что задачу определения расстояния между всеми парами вершин можно решить, используя n раз один из ранее изложенных методов нахождения расстояний от фиксированной вершины. Таким образом, мы получаем алгоритм со сложностью O(n4) (при использовании метода Форда — Беллмана) или O(n3) для бесконтурных графов или неотрицательных весов. Однако оказывается, что в общем случае n–кратное использование метода Форда — Беллмана не является наилучшим методом.

Рассмотрим ориентированный граф G = <V, E>, где V = {v1, ..., vn}, и предположим, что A = [aij] есть матрица весов (aij = a(vi, vj)). Обозначив через dij(m) длину кратчайшего пути из vi  в vj, содержащего не более m дуг, получаем следующие очевидные уравнения:

Если операцию min трактовать как «сумму», операцию «+» — как «произведение», то матрица [dij(m+1)] является «произведением» матриц [dij(m)] и A = [aij]. Обозначим такое «произведение» двух матриц A и B через A*B и отметим, что для этой операции единичным элементом служит матрица

Тогда [dij(0)] = U и

Произведение A*B двух матриц размерности n ´ n можно вычислить за время O(n3) (n сложений и n – 1 сравнений на каждый из n2 элементов произведения A*B). Следовательно, матрицу и тем самым расстояние между всеми парами вершин можно вычислить за время O(n4).

Пока сложность этого алгоритма такая же, как и для случая n–кратного использования алгоритма Форда — Беллмана. Однако мы можем ее снизить, если заметим, что операция * ассоциативна (т.е. (A * B) * C = A * (B * C)). Этот факт позволяет вычислять произведение, поочередно возводя матрицу A в квадрат и тем самым заменяя n – 1 умножение матрицы élog nù умножениями. Таким образом, мы получаем алгоритм сложности O(n3 log n), отыскивающий расстояния между всеми парами вершин в графе без контуров отрицательной длины.