广度优先分析

Question

我有 Cormen 的以下 BFS 函数。

定义从 s 到 v 的最短路径距离 path(s,v) 作为从顶点 s 到顶点 v 的任何路径中的最小边数，否则如果没有从 s 到 v 的路径。长度为 path 的路径从 s 到 v 的 (s,v) 被称为从 s 到 v 的最短路径。

以下是给定的引理

设 G = (V,E) 为有向图或无向图，并设 s 属于 V 为任意顶点。然后，对于任何边 (u, v) E，

path(s,v) <= path(s,u) + 1 。

我的问题是为什么我们在上面的公式中必须有<=，我教过“=”是可以的，谁能告诉我一个场景为什么我们需要<=？

下面是BFS算法

Leema 2 ：

设 G = (V,E) 为有向图或无向图，并假设 BFS 在 G 上运行，给定源顶点 s 属于 V。然后在终止时，对于属于 V 的每个顶点 v，值 d[ v] 计算出由BFS满足d[v]>=path(s,v)。

证明：

我们对顶点被放入队列 Q 的次数进行归纳。我们的归纳假设是 d[v] >= path(s,v)，因为所有 v 都属于 V。

归纳的基础是紧接着s之后的情况被放入BFS第8行的Q中。

归纳假设在这里成立，因为 d[s] = 0 = path(s, s) 且 d[v] = path (s, v)，所有 v 都属于 V - {s}。

我的问题是作者所说的“我们对顶点放置在队列 Q 中的次数使用归纳法”是什么意思？它与归纳假设有何关系？

谢谢！

BFS(G,s)
1  for each vertex u  V[G] - {s}
2       do color[u]  WHITE
3          d[u]  
4          [u]  NIL
5  color[s]  GRAY
6  d[s]  0
7  [s]  NIL
8  Q  {s}
9  while Q  
10      do u  head[Q]
11         for each v  Adj[u]
12             do if color[v] = WHITE
13                   then color[v]  GRAY
14                        d[v]  d[u] + 1
15                        [v]  u
16                        ENQUEUE(Q,v)
17         DEQUEUE(Q)
18         color[u]  BLACK

Answer 1

对于第一个问题，考虑一个只有三个顶点的完整图。在此图中，path(s,v) = path(s,u) + 1 是真的吗？