Вычисление матрицы путей из матрицы смежности

Question

Я изучаю способ вычисления Матрицы Пути из Матрицы Смежности (скажем, AM1).

Матрица путей графа G с n вершинами является булевой матрицей n*n, элементы которой могут быть определены как:

  p[i][j]=1(if there is a path from i to j)
  p[i][j]=0(otherwise)

И шаги, которые я изучил, следующие:

Если мы умножим матрицу смежности A[][] самостоятельно, мы получим A^2(скажем, AM2), каждая вершина которого A[i][j] в основном представляет количество путей длины пути 2 от i до j.

Аналогично, если мы умножим матрицу смежности 3 раза, то есть получим A^3(скажем, AM3), каждая вершина которого A[i][j] в основном представляет количество путей длины пути 3 от i до j... и так далее.

Теперь мы определим Матрицу X так, чтобы:

X = AM1 + AM2 + AM3... AMn (где n- количество вершин)

Из этой X-матрицы мы вычисляем матрицу пути / достижимости , заменяя все ненулевые вершины на 1.

Что я не могу понять, так это то, как замена всех ненулевых вершин на 1 дает нам матрицу путей.?. И почему мы вычисляем или добавляем всю матрицу до AMn.?

Я понимаю, что X[i][j] символизирует количество путей, длина пути n или меньше n, от i до j, но почему мы вычисляем только до n, а не больше или меньше?

Пожалуйста, объясни!

Answer 1

Что я не могу понять, так это то, как замена всех ненулевых вершин на 1 дает нам матрицу путей?

Если A^k дает нам количество путей из i->j после k шаги, ненулевое число означает, что соответствующая запись в матрице пути должна быть Истиной, так как существует по крайней мере один путь. Теперь это должно быть правдой для k=1 (петли), k=2, k=3... вплоть до k=N...

Но почему мы вычисляем только до п, а не больше или меньше?

Если есть путь от i->j на графе только с N вершинами наихудший случай состоит в том, что существует путь, который проходит каждую промежуточную вершину, то есть N-1 шагов, следовательно, необходимо вычислить A^N,

Обратите внимание, что существуют и другие, менее дорогие способы расчета так называемой матрицы пути. По сути (для неориентированных графов) вы ищете связанные компоненты графа, которые могут быть выполнены за линейное время с поиском в глубину. Чтобы рассчитать все A^k каждое умножение потребует примерно O(N^3) время, N раз в общей сложности около O(N^4), Этого можно избежать с помощью диагонализации матрицы, O(N^3), чьи собственные значения и собственные векторы дают некоторое представление о структуре графа (гораздо больше, чем сама матрица путей!).