用全点对最短路径估计流形上的距离
scikit-learn 的 Isomap 先建立近邻图，再用最短路径近似测地距离；选择 path_method="FW" 时由 SciPy 执行 Floyd–Warshall，结果用于非线性降维。
工程问题#
高维样本可能沿着弯曲的低维流形分布。直接使用两点的欧氏距离可能穿过流形内部，无法反映沿数据表面行走的距离；Isomap 需要先估计所有样本对的测地距离，再构造低维表示。
实际实现#
Isomap 以样本为节点、近邻距离为边权建立图，通过最短路径把局部距离累加成全局距离。path_method="FW" 会调用 SciPy 的 Floyd–Warshall，在距离矩阵上逐个引入中间节点；随后将最短距离平方并乘以 -0.5，交给预计算核模式的 KernelPCA。
处理流程#
- 按 k 近邻或半径邻域构造带距离权重的图，并处理连通分量
- 选择 path_method="FW"，以无向图调用 SciPy shortest_path
- 逐个引入中间节点，更新全部样本对的最短距离
- 将距离矩阵转换为核矩阵，由 KernelPCA 求低维坐标
源码片段#
固定版本 · 原文摘录243 if self.n_neighbors is not None:244 nbg = kneighbors_graph(245 self.nbrs_,246 self.n_neighbors,247 metric=self.metric,248 p=self.p,249 metric_params=self.metric_params,250 mode="distance",251 n_jobs=self.n_jobs,252 )253 else:254 nbg = radius_neighbors_graph(255 self.nbrs_,256 radius=self.radius,257 metric=self.metric,258 p=self.p,259 metric_params=self.metric_params,260 mode="distance",261 n_jobs=self.n_jobs,262 )按近邻数量或半径构造图，mode="distance" 让边权记录样本距离。下游最短路径累加这些局部距离，而不是直接使用高维空间中任意两点的直线距离。
300 self.dist_matrix_ = shortest_path(nbg, method=self.path_method, directed=False)301302 if self.nbrs_._fit_X.dtype == np.float32:303 self.dist_matrix_ = self.dist_matrix_.astype(304 self.nbrs_._fit_X.dtype, copy=False305 )306307 G = self.dist_matrix_**2308 G *= -0.5309310 self.embedding_ = self.kernel_pca_.fit_transform(G)311 self._n_features_out = self.embedding_.shape[1]把 path_method 传给 SciPy，求无向近邻图的全点对最短距离；距离平方后乘以 -0.5，交给使用预计算核的 KernelPCA 得到低维坐标。这是算法结果的实际使用位置。
198 if indices is not None or Nk < N * N / 4:199 if np.any(edges < 0):200 method = 'J'201 else:202 method = 'D'203 else:204 method = 'FW'205206 if method == 'FW':207 if indices is not None:208 raise ValueError("Cannot specify indices with method == 'FW'.")209 return floyd_warshall(csgraph, directed,210 return_predecessors=return_predecessors,211 unweighted=unweighted,212 overwrite=overwrite)213214 elif method == 'D':215 return dijkstra(csgraph, directed,216 return_predecessors=return_predecessors,217 unweighted=unweighted, indices=indices)显式 method="FW" 调用 floyd_warshall；默认 auto 在前面的分支统计节点和边。本例不指定源点子集，边数小于 n²/4 且没有负边时选择 Dijkstra；稀疏存储格式本身不决定算法。
415 else:416 for k in range(N):417 for i in range(N):418 if dist_matrix[i, k] == INFINITY:419 continue420 for j in range(N):421 d_ijk = dist_matrix[i, k] + dist_matrix[k, j]422 if d_ijk < dist_matrix[i, j]:423 dist_matrix[i, j] = d_ijkIsomap 只需要距离矩阵，没有请求前驱数组，因此对应这一分支。依次允许节点 k 作为中间点，若 i→k→j 更短便更新距离；最终得到全部样本对的图距离。
四段连续原文分别展示近邻图构建、距离结果的实际使用、SciPy 的方法分派和 Floyd–Warshall 的矩阵更新。已保留两个项目的固定版本完整源文件与许可；片段没有覆盖近邻搜索、连通分量修复或 KernelPCA 内部。
收益与取舍#
工程分析带来的收益
- 用图上的路径累加局部距离，能够近似沿流形表面的距离
- 全点对距离矩阵可以直接用于 Isomap 后续的核矩阵计算
付出的代价
- 设样本数为 n，Floyd–Warshall 的最坏时间为 O(n³)，距离矩阵占 O(n²) 空间；近邻搜索与特征分解还有各自的成本
- 邻域太小可能使图断开，太大则可能引入跨流形的捷径，影响距离估计
- 使用 Dijkstra 可改善稀疏图上的路径计算，但这个实现仍保存全点对距离，不能因此省掉 O(n²) 的结果空间
可比较的选择
逐源 Dijkstrapath_method="D" 对非负边的近邻图重复做单源搜索，通常更适合稀疏图；目标仍是同一个全点对距离矩阵。
线性 PCA无需先求近邻图最短路径，但优化的是线性投影，不能等价代替 Isomap 对流形测地距离的近似。
版本与适用范围#
核验 scikit-learn 1.6.1 与 SciPy v1.15.2 的调用和实现，重点分析显式 path_method="FW" 的训练路径。Isomap 默认是 auto；此版 SciPy 按图规模、边数及负边情况选算法，本例不指定源点子集，边数小于 n²/4 且没有负边时会选 Dijkstra（n 为样本数），不能说 Isomap 默认总是 Floyd–Warshall。图不连通时，上层可能补连边；稀疏预计算距离无法补全时会报错。这里的测地距离是由近邻图得到的近似值。
参考来源#
源码、官方文档与原始论文scipy/sparse/csgraph/_shortest_path.pyx · shortest_path / _floyd_warshall