BFS无法找到的最短路径？

Question

BFS无法找到的最短路径？

algorithmsearchgraph-theorygraph-algorithmbreadth-first-search

5

我早些时候参加了一场考试，有一道题让我和我谈过的其他人都感到困惑。问题如下：

给出一个无权图 G 和两个顶点 s 和 f，使得在特定边相邻的顶点访问顺序下，从 s 开始的广度优先搜索永远找不到 s 和 f 之间的最短路径。

对我们来说，这似乎是不可能的。我的第一个想法是，如果最短路径包含一个作为其第 n 步的顶点，而该顶点可以从 s 中在 m 步内到达，其中 m < n，则 BFS 将永远无法找到该路径，因为该顶点已被标记为已访问。但如果是这种情况，所述路径根本不是最短路径，因为通过在 m 步内到达该顶点，然后继续正常进行，可以获得更短的路径。

我们的教授是否提出了一个不可能的问题（可能是笔误），还是我漏掉了什么？

编辑： 为了消除任何可能的歧义，该问题并不要求给出BFS无法从s到f找到最短路径的例子。相反，它要求给出一个例子，其中存在从s到f的某些最短路径，BFS永远不会找到。因此，仅仅因为BFS是完备和最优的，并不能排除这种可能性，除非我误解了这些术语的含义。

编辑2： 还可以假设我们使用的BFS算法不会处理同一个节点两次。例如，请参见BFS Wiki上的算法概述。

- hexaflexagonal

1

即使BFS没有跟踪已访问的节点，它最终也会接触到每条可行的路径。我认为这一定是一个打字错误。 - Mooing Duck

的确。深度优先搜索可能会“迷失”（当然，仅当它无法检测到循环时）。广度优先搜索则不会。广度优先搜索被认为是一种完全搜索，这意味着如果存在解，则它保证能够始终找到解（假设时间足够长）。 - aruisdante

你的推理几乎正确 - 如果有多条路径长度相等，那么可能会有不止一条最短路径，因此如果先访问另一条路径，则可能会错过其中一条路径（例如，对于菱形形状）。然而，他明确表示它不会在任何访问顺序中被找到，因此这也行不通。 - Leeor

没错，@Leeor。钻石形是我的第一反应，但正如你所指出的那样，这种解决方案和类似的解决方案在任意访问顺序下都无法保持稳定。 - hexaflexagonal

1

图必须是有限的吗？ - amit

如果从s到f存在长度为m的最短路径，你可以通过反证法轻松证明BFS会找到它，前提是所有边的权重相同（我认为这就是无权图的意思）。 - Ari

2个回答

2

我认为@hexaflexagonal可能错误地陈述了问题。

这应该是CLRS中的一个问题：

问题和解决方案：

由于BFS的性质，有些E_{\pi}集合不会被BFS产生。对于具有多个最短路径解决方案的循环图，就是这种情况。

- Nicole

这真是一个惊人的发现，多年后回来看到这些！你一定是对的——我们那时候还是个累瘦的本科生，无法正确处理这个问题~ - hexaflexagonal

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- AbcAeffchen · Accepted Answer

示例

设G = (V,E)为一个图，其中V = ℕ ∪ {-1, 0}，E = { {-1,t}, {t,0} | t ∈ ℕ }，并且s = -1，f = 0。存在无限条长度为2的从 s 到 f 的路径，但由于s有无限多个邻居，BFS将永远不会到达f。

不存在有限示例

不存在有限图使得 BFS 无法找到从s到f的最短路径。假设G为一个有限图，并且s = a₀ → a₁ → ... → a_n → a_n+1 = f是从s到f的最短路径。那么存在如下的BFS执行顺序：

对于所有i从0到n，先访问a_i+1，然后再访问a_i的所有其他直接邻居。

由于G是一个有限图，每个节点a_i的直接邻居也是有限的。因此，BFS将完成对所有邻居节点的遍历，然后继续处理路径上的下一个节点。因为这是一条最短的路径，所以这将是连接s和f的第一条路径。所以不存在使得 BFS 无法找到从s到f的最短路径的有限图。

路径长度不能短于两条边

也不能存在从s到f长度小于2的路径。
若考虑 s 和 f 不是同一个节点，则能想到最短路径的长度为1。但是这意味着f是s的直接邻居，这样就存在一个BFS先访问f，然后再继续其他无限多的邻居节点。