无向无权图多最短路径代码的两个技术疑问

问题1：无法触发"found it again"打印语句的原因及可行案例 #

在你的BFS实现中，"found it again"的触发条件是同一个节点被第二条等长（最短）路径访问到。你之前没找到案例，大概率是没构造出存在「多个同长度最短路径到达同一中间节点」的图。

举个具体案例：

a -- b -- d -- f
a -- c -- d

这个图里，从a到d有两条最短路径：a->b->d和a->c->d，长度都是2。当BFS执行时：

1. 先处理起点a，将b、c的距离设为1，标记为已访问；
2. 处理b，将d的距离设为2，标记为已访问，记录b为d的父节点；
3. 处理c，访问邻居d时，发现d已被访问，但distance.get(c)+1 == distance.get(d)（1+1=2），这时候就会触发"found it again"的打印，同时把c也加入d的父节点列表。

问题2：else分支直接添加父节点的风险 #

你的担心是对的，仅靠visited检查无法避免引入更长路径的父节点，必须加上distance.get(child) == distance.get(node)+1的判断。

原因很简单：BFS是按层次遍历的，节点的最短距离在第一次被访问时就确定了。如果后续再遇到已访问的child节点，只有当当前node的距离+1等于child的最短距离时，才说明这是另一条最短路径的父节点；如果不判断，当遇到更长路径到达child时（比如child已经通过短路径被访问过，后续某个更远的节点又指向它），会把这个非最短路径的node加入父节点列表，最终生成的路径里就会包含更长的非最短路径。

举个反例：

a -- b -- d -- f
a -- c -- e -- d

从a到d的最短路径是a->b->d（长度2），而a->c->e->d是长度3的长路径。当BFS处理到e时，d已经被访问过（距离2），此时distance.get(e)+1 = 3，远大于d的最短距离2。如果你的else分支直接添加父节点，d的父节点就会错误地包含e，后续生成路径时就会出现a->c->e->d->f这种非最短路径。

所以正确的逻辑应该是：

if (!visited.contains(child)) {
    // 第一次访问，设置距离、标记已访问、添加父节点
} else if (distance.get(child) == distance.get(node) + 1) {
    // 找到另一条最短路径的父节点，打印"found it again"并添加父节点
}
// 其他情况（路径更长）直接跳过

内容的提问来源于stack exchange，提问作者curiousengineer