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

Question

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

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

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 (где п число вершин)

С этой 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 ,

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