通过邻接矩阵计算路径数
0. 概念
邻接矩阵 (adjacency matrix)
在图论和计算机科学中，邻接矩阵（adjacency matrix）是一种方阵，用来表示有限图。它的每个元素代表各点之间是否有边相连。
从定义上，他的形式是：
阶为$n$的图$G$的邻接矩阵$A$是$ n\times n$的。将$G$的顶点标$v_{1},v_{2},…,v_{n}$。若$ (v_{i},v_{j})\in E(G)$，$ A_{ij}=1$，否则$ A_{ij}=0$。也可以用大于 0 的值表示边的权值，例如可以用边权值表示一个点到另一个点的距离。
1. 邻接矩阵计算方法与远离
计算方法
对邻接矩阵$A$进行$n$次幂运算，得到$A^{n}$，则$(A^{n})_{ij}$表示从顶点$v_{i}$到顶点$v_{j}$的长度为$n$的路径数。
原理
为什么上述计算方法是正确的呢？上述计算到底经历了什么呢？
假设我们有邻接矩阵$A = \begin{pmatrix}0 & 1 & 1 \\1 & 0 & 1\\1&1 & 0\end{pmatrix}$，即如图所示的图：
假设我们要计算从顶点$A$到顶点$C$的长度为 2 的路径数。根据上面的公式，我们可以计算$A^{2}$，即$\begin{pmatrix}0 & 1 & 1 \\1 & 0 & 1\\1&1 & 0\end{pmatrix}^{2} = \begin{pmatrix}2 & 1 & 1 \\1 & 2 & 1\\1&1 & 2\end{pmatrix}$。
$A^{2}$的第一行第三列的元素为 1，表示从顶点$A$到顶点$C$的长度为 2 的路径数为 1。他的计算是：$A^{2}_{13} = A_{11} \times A_{13} + A_{12} \times A_{23} + A_{13} \times A_{33}$。
$A_{11} \times A_{13} + A_{12} \times A_{23} + A_{13} \times A_{33}$ 有三项，第二项是$A_{12} \times A_{23}$，$A{12}$代表从顶点$A$到顶点$B$的路径数，$A{23}$代表从顶点$B$到顶点$C$的路径数。这两个路径数相乘，代表的就是 A->B->C 的路径数。其他两项同理，一个是 A->A->C 的路径数，一个是 A->C->C 的路径数。
也就是说，矩阵的乘法刚刚好计算了从一个顶点到另一个顶点的路径数。证明幂运算的正确性，可以通过数学归纳法证明。