路径、距离与最短路径算法

路径与最短路径

路径（path）是一串节点，相邻节点之间都有边相连；路径包含的边数称为路径长度。两个节点之间的距离（distance）$d_{ij}$ 是它们之间最短路径的长度，也叫测地距离（geodesic distance）。若两点之间不存在路径，约定 $d_{ij} = \infty$。有向网络中一般 $d_{ij}\ne d_{ji}$，甚至可能一个有限、一个无穷。

邻接矩阵的幂有一个漂亮的性质：$(A^h)_{ij}$ 等于从 $i$ 到 $j$ 长度恰为 $h$ 的途径（walk，允许重复经过节点和边）条数。因此 $d_{ij}$ 就是使 $(A^h)_{ij} > 0$ 的最小 $h$。途径计数也是谱类中心性的出发点。

离心率、直径与平均路径长度

直径对单个“偏远”节点很敏感，平均路径长度更能反映典型情况。网络不连通时 $L$ 为无穷大，常见处理有两种：只在最大连通分支上计算 $L$；或改用全局效率（见全局效率与局部效率），不连通的节点对贡献 0。后者在脑网络研究中很常用。

广度优先搜索

怎样计算距离？广度优先搜索（breadth-first search，BFS）是最基本的算法：

1. 把源点 $s$ 标记为距离 0，放入队列；
2. 从队列取出一个节点 $v$，把它尚未标记的邻居标记为 $d(v)+1$，放入队列尾部；
3. 重复第 2 步直到队列为空。

BFS 像水波一样从源点“一层一层”向外扩散，每一层的节点距离相同。它的计算量与 $N+M$ 成正比，在稀疏网络上非常快。对每个节点各做一次 BFS，就得到所有节点对之间的距离。加权网络的最短路径要用 Dijkstra 算法（单源，要求长度非负）或 Floyd–Warshall 算法（全点对，$O(N^3)$，适合几百个节点的稠密脑网络），并且要先想清楚“距离”与“权重”的关系：相关系数越大表示连接越强，转换成长度时通常取倒数或 $-\log w$（见加权网络的指标）。