我有来自 Cormen 的以下 BFS 功能。
从 s 到 v 的最短路径距离 path(s,v) 定义为从顶点 s 到顶点 v 的任何路径中的最小边数，或者如果没有从 s 到 v 的路径。 (s,v) 从 s 到 v 被称为从 s 到 v 的最短路径。
以下是给定的引理
令 G = (V,E) 为有向或无向图，令 s 属于 V 为任意顶点。然后，对于任何边 (u, v) E，
路径(s,v) <= 路径(s,u) + 1 。
我的问题是为什么我们必须在上面的公式中有 <= ，我教过 "=" 是可以的，谁能告诉我一个场景为什么我们需要 <= ？
下面是BFS算法
利马 2：
令 G = (V,E) 是有向或无向图，并假设 BFS 从给定源顶点 s 属于 V 的 G 上运行。然后在终止时，对于每个顶点 v 属于 V，值 d[v ] 由 BFS 计算满足 d[v] >= path (s, v)。
证明：
我们对顶点在队列 Q 中放置的次数使用归纳法。我们的归纳假设是所有 v 都属于 V 的 d[v] >= path(s,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