用 SciPy 稀疏图找最短词梯：从词表到前驱回溯-未完纪

原文：SciPy 官方教程《Compressed Sparse Graph Routines (scipy.sparse.csgraph)》。作者归属：SciPy 文档贡献者，页面版权归 The SciPy community。未完纪中文翻译整理；保留 BSD 3-Clause 版权条件与免责声明。

读取日期：2026-10-05，源站页头为 SciPy v1.18.0 Manual。示例依赖 NumPy、SciPy 和本地词表；系统词典路径不跨平台通用。本稿仅做静态代码审查，未运行图算法；下文词数、路径和距离均标明为原文示例。

编辑原创技术示意图，依据本文所列官方源文绘制；非截图。绘制：未完纪编辑整理（Codex 辅助绘制）。

一个每步只换一个字母的最短路径问题

词梯（Word Ladder）是 Lewis Carroll 发明的文字游戏：每一步只替换一个字母，且变化后的字符串仍须在选定词表中。原文从下面这条路径开始：

ape → apt → ait → bit → big → bag → mag → man

这条链有 8 个词、7 次变换。它说明 ape 与 man 可以相连，却没有证明是最短路径。把每个词当作顶点，两词仅一个字母不同时连边，问题就变成在图中寻找边数最少的路径。scipy.sparse.csgraph 提供了所需算法。

读入并约束词表

某些 Linux 系统在 /usr/share/dict 或 /var/lib/dict 提供一行一词的词典，例如 /usr/share/dict/words；其他系统可能没有这个文件。也可以选择有明确来源与使用许可的游戏词表，但不同词表对专有名词、缩写、变体词的接受规则不同，最终答案会跟着变化。

原文先读文件，去掉行首尾空白，留下长度为 3、首字母小写且全部为字母的词，再统一为小写。其样本包含 586 个词。这个数字和后续所有路径都不是跨词表常量。下面的编辑修订版保留这些筛选意图，并明确限制为 ASCII 字母、去重和排序：

from pathlib import Path
import numpy as np

# 改成自己的词典文件；这是读取输入，不是系统安装步骤。
dictionary_path = Path('/usr/share/dict/words')
with dictionary_path.open(encoding='utf-8') as f:
    raw_words = [line.strip() for line in f]

words = np.asarray(sorted({
    word.lower()
    for word in raw_words
    if len(word) == 3
    and word.isascii()
    and word.isalpha()
    and word[0].islower()
}))
if words.size == 0:
    raise ValueError('筛选后没有符合条件的三字母词')
print(words.size)

使用已知文件编码；若词典不是 UTF-8，应根据它的实际编码修改参数，不应悄悄忽略无法解码的字节。首字母小写筛选沿用原文用于排除部分专有名词的启发式，不能替代语言学上的词性判断。

字符向量与 Hamming 距离

原文把词数组转成 NumPy Unicode 数组并排序，典型 dtype 为 <U3。然后用 uint8 查看底层字节，再每隔一个字符的字节宽度取一个字节：

# 原文做法，展示原理；不要对任意 Unicode 直接套用。
word_bytes = np.ndarray(
    (word_list.size, word_list.itemsize),
    dtype='uint8', buffer=word_list.data
)
word_bytes = word_bytes[:, ::word_list.itemsize // 3]

在原文假设的布局下，每个字符占四字节，受控 ASCII 字符的首字节足以区分字母，于是得到 N×3 的向量。实际风险在于 isalpha() 并不只接受 ASCII，而 Unicode 字符的其他字节、字节序与底层布局都可能改变比较含义。本文不依赖这一技巧，改为明确编码三个 ASCII 字符：

word_bytes = np.asarray(
    [list(word.encode('ascii')) for word in words],
    dtype=np.uint8,
)
# 形状为 (词数, 3)

Hamming 距离是两个向量中不同位置所占的比例。三字母词若只差一个位置，距离就是 1/3；差两个是 2/3；完全相同则为 0。原文没有使用浮点相等比较，而用小于 1.5/3 的阈值判定边，前提是词表没有重复项。本文已经去重，同时显式排除零距离：

from scipy.spatial.distance import pdist, squareform
from scipy.sparse import csr_array

hamming_dist = pdist(word_bytes, metric='hamming')
one_letter_apart = (hamming_dist > 0) & (hamming_dist < 1.5 / 3)
graph = csr_array(squareform(one_letter_apart))

pdist 先计算不重复的两两距离，squareform 把它展开为对称邻接矩阵，csr_array 再把邻接矩阵存成压缩稀疏行形式。这里每条边权相同，表示一次换字母；矩阵对称，问题是无向图。

规模边界：最终 graph 是稀疏的，不代表建图过程是线性内存。pdist 的成对距离和 squareform 的方阵都随词数呈二次增长。该写法适合小型教学词表；更大词表应考虑按“去掉一个位置后的模式”分桶或逐字母生成候选邻居，直接构造稀疏边，不能仅凭 csr_array 名称推断内存可控。

定位起点与终点，再运行 Dijkstra

排序数组可以使用 searchsorted 快速找词，但返回的是插入位置，即使目标不存在也会返回一个整数。若插入位置恰好等于数组长度，直接索引还会越界。先验证，再求解：

def word_index(word):
    index = int(words.searchsorted(word))
    if index >= words.size or words[index] != word:
        raise ValueError(f'词表中不存在目标词：{word}')
    return index

source = word_index('ape')
target = word_index('man')

from scipy.sparse.csgraph import dijkstra
distances, predecessors = dijkstra(
    graph,
    directed=False,
    indices=source,
    return_predecessors=True,
)
if not np.isfinite(distances[target]):
    raise ValueError('两个词属于不同连通分量，没有词梯路径')
print(distances[target])

indices 只选择一个源点，因此这次返回的是从 ape 到所有词的距离与前驱数组，而不是所有词对的矩阵。Dijkstra 可处理本例的非负边权；这里等权边使最短距离等于变换次数。原文对其 586 词样本输出 5.0。

根据前驱回溯路径

前驱数组记录了从指定起点到达各顶点的最短路径上，上一站是谁。从 target 开始倒着走，最后反转即可得到正向路径。原文直接 while 回溯；本文在已经检查距离有限的前提下，再检查前驱索引与步数上限，避免无路径哨兵或异常前驱被当作合法 Python 负索引：

def reconstruct_path(predecessor_row, start, finish):
    route = []
    current = int(finish)
    for _ in range(words.size):
        route.append(str(words[current]))
        if current == start:
            return route[::-1]
        previous = int(predecessor_row[current])
        if previous < 0 or previous >= words.size:
            raise ValueError('前驱不存在或不合法，无法还原路径')
        current = previous
    raise ValueError('前驱链超过顶点数，可能存在异常循环')

route = reconstruct_path(predecessors, source, target)
print(route)

# 编辑新增的可检查条件；没有在本次执行。
assert len(route) - 1 == int(distances[target])
assert all(
    sum(left != right for left, right in zip(a, b)) == 1
    for a, b in zip(route, route[1:])
)

原文得到：["ape", "apt", "opt", "oat", "mat", "man"]，即 6 个词、5 条边。比开头 7 步路径少 2 步。原页文字把减少量写为“三步”，与展示链的边数不一致，本稿按实际列表更正。

哪些词互相到不了：连通分量

同一连通分量内的两个词可以用某条词梯相连，不同分量之间没有路径。用 connected_components 取得分量个数及每个顶点的标签：

from scipy.sparse.csgraph import connected_components

n_components, labels = connected_components(graph, directed=False)
sizes = np.bincount(labels, minlength=n_components)
print(n_components)
print(sizes.tolist())

largest = int(sizes.argmax())
small_groups = [
    words[labels == label].tolist()
    for label in range(n_components)
    if label != largest
]
print(small_groups)

原文样本有 15 个连通分量，其中一个包含 571 个词，另一个包含 ems 和 emu，其余是单词分量：aha、chi、ebb、gnu、ism、khz、nth、ova、qua、ugh、ups、urn、use。原文通过跳过标签 0 显示小分量；本文通过大小找到最大分量，避免把标签编号当作规模保证。

“小分量”不意味着其中每个词都孤立：ems 与 emu 仍彼此相连，只是和大分量不连通。连通性也只针对当前词表与“恰好替换一个位置”的规则，不能推断真实语言里不存在其他词梯。

在所有能到达的词对中，哪一对最远

去掉 indices 参数可计算全点最短路。结果含 N×N 的距离矩阵和前驱矩阵；不连通点对的距离为无穷大。这里必须先筛掉无穷大，才有意义地求“最长的有限最短路径”：

# 只适用于内存预算允许的小图；会产生两份 N×N 结果。
all_distances, all_predecessors = dijkstra(
    graph, directed=False, return_predecessors=True
)
finite = np.isfinite(all_distances)
max_distance = all_distances[finite].max()
left_indices, right_indices = np.nonzero(all_distances == max_distance)

print(max_distance)
print(list(zip(words[left_indices], words[right_indices])))

first_source = int(left_indices[0])
first_target = int(right_indices[0])
long_route = reconstruct_path(
    all_predecessors[first_source], first_source, first_target
)
print(long_route)

原文最大有限距离为 13.0。展示的有向端点对有 8 项，来自 {imp, ump} 与 {ohm, ohs} 两组词的交叉组合及反向；按无向词对计算是 4 对，不是只有一个固定答案。其第一条还原路径为：

imp → amp → asp → ass → ads → add → aid → mid → mod → moo → too → tho → oho → ohm

它有 14 个词、13 条边。原文保留这些词是为了展示真实词表结果，并非说明所有词表都接受这些拼写。不同词典、筛选规则及同距离路径的选择，可能给出其他最短路径。

如果图不连通，这个量是各连通分量内部有限距离的最大值，不应未经定义就称为整个图的有限直径。对大图，可以按源点分批求距离、逐步维护最大值，再只为选定起点求前驱；仍要权衡计算总量，不能为了找极值就无条件分配全点矩阵。

同一套方法还可以处理什么

词梯把“可直接变换”编码成边，把“最少步骤”编码成路径长度。稀疏图工具也可用于其他数学、数据分析与机器学习问题，但必须重新定义顶点、边与权重，并选择满足权重和方向条件的算法。本例的正确性依赖受控词表、准确字符比较和路径存在检查；稀疏容器只解决部分存储问题，不会自动解决建图成本。

许可证

下面保留 SciPy 仓库 BSD 3-Clause 的版权条件与免责声明。正文中的健壮性检查、显式 ASCII 编码和文字勘误为编辑改动，未执行验证。

Copyright (c) 2001-2002 Enthought, Inc. 2003, SciPy Developers.
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:

1. Redistributions of source code must retain the above copyright
   notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above
   copyright notice, this list of conditions and the following
   disclaimer in the documentation and/or other materials provided
   with the distribution.
3. Neither the name of the copyright holder nor the names of its
   contributors may be used to endorse or promote products derived
   from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

文章版权归作者所有，未经允许请勿转载。

THE END