[Math] Calculating the Distance Matrix from Adjacency Matrix

adjacency matrixalgebraic-graph-theorygraph theorymatricespython

How would I calculate the distance matrix of a connected, simple and undirected graph from the adjacency matrix? I have 56 nodes, if that is helpful, and would need to the answer to return an array.
Thank you!

Best Answer

I believe you can also take the matrix multiple of the matrix by itself n times. I have read that for an entry [j,v] in matrix A:

A^n[j,v] = number of steps in path of length n from j to v.

With that in mind, iterate the matrix multiple A@A and freeze new entries (the shortest path from j to v) into a result matrix as they occur and masking by the result matrix so you only get the newest path for some n. This would result in a matrix where each entry [j,v] is the shortest path from j to v.

In my experience, A@A = A for some large n so the calculation is cyclic which can be a terminating condition, I suspect its the maximum path but cannot guarantee as I've only tested on a subset of possible graphs. I would calculate the maximum path possible in any graph: the number of nodes (a graph which is sequentially connected with one loop) and iterate that many times, which guarantees considering all possible paths in all graphs. I've done this with directed graphs but this should hold for symmetry about the main diagonal.

I hate to quote an unreferenced wikipedia article but this has been working for me in practice. https://en.wikipedia.org/wiki/Adjacency_matrix#Matrix_powers

The implementation is trivial enough I think its worth a try. If you try it please let me know if this fails your implementation.

Related Question