Вольный перевод из Estimating all pairs shortest paths in restricted graph
families: a unified approach (2005):
В общем случае, чтобы найти кратчайшее
расстояние между всеми парами вершин в
графе, требуется O(M(n)log n)
, где
M(n)
время умножения матрицы (с
маленькими целыми числами) т.е.
O(n**2.376)
(алгоритм Копперсмита-Винограда). Для сравнения, простой поиск в ширину ведёт к Θ(nm)
алгоритму,
что является Θ(n**3)
для плотных графов. n
- кол-во вершин, m
- кол-во рёбер. Оптимальное время O(n**2)
может быть достигнуто для некоторых типов графов.
т.е. линейных по числу вершин алгоритм (основанный на сравнении путей) невозможен для произвольных графов (note: кол-во рёбер квадратично кол-ву вершин в плотных графах).