algorithm - BFS分析

Question

我有来自 Cormen 的以下 BFS 函数。

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

下面是给出的引理

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

路径(s,v) <= 路径(s,u) + 1 。

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

下面是BFS算法

利马 2:

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

证明:

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

归纳的依据是BFS第8行将s放入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 是否成立？