sabakka> O(1) по памяти означает, что объём используемой алгоритмом доп.памяти не должен зависеть от NUM_VERTICES.
У тебя просто представление исходных данных уже не будет, как О(1) в твоём понимании. Поскольку исходные данные. Когда учили, то у нас О(1) было именно статическое размещение (хотя эта метрика официальной не была). Потому, я думаю, что рекурсия запрещена, т.к. это неявное размещение динамическое на стеке. Поэтому и можно всё дефайнером определить.
sabakka> Алгоритм Уоршала позволяет это сделать, но как после заполнения вектора достижимости для требуемой исходной вершины вернуть исходную матрицу смежности? Алгоритм, который портит после себя исходные данные, переданные ему по ссылке, очевидно, не годится.
Ты говоришь про вектор достижимости. Понятно, что для одного элемента, это строка/столбец из матрицы достижимости. В твоём понимании, О(1) не получится, если только не гадить в исходные данные.
Можно ещё пойти и путём ленивых вычислений. Для вычисления вершина-вершина в лоб надо сделать по "или" из матриц композиций отношений до степени N. Для вычисления элемента уже надо хранить вектор степеней. Т.е. не получиться обойтись одной переменной. Для Флойда-Уоршелла тоже мжно зафиксировать внутрение переменные цикла, но внешнюю не выйдет — нужно замыкание. Посмотрел на Кнута, Джонса и Данцига — вроде те же проблемы.
Ну, нет правда у нас ограничений на количество ввода-вывода.
Можно исходную там хранить.
Или вывести заранее исходную, а потом строить замыкание.
sabakka> Это означает, что исходная матрица смежности содержит избыточную информацию.
Ты, видимо, считаешь то, что там симметрия получается получается? Кто тебе мешает работать с треугольной матрицей?