BFS分析

Question

我有以下科门的BFS功能。

从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算法

Leema 2：

设G= ( V，E)是有向图或无向图，并假定BFS是从给定的源顶点s属于V的G上运行的，在终止时，对于每个顶点v属于V，则BFS计算的值dv满足dv >=路(s，v)。

证明：

我们对一个顶点放置在队列Q中的次数使用归纳法。我们的归纳假设是，对于所有V都属于V的dv >=路径(s，v)。

归纳的基础是将s放在BFS第8行的Q中之后的情况。

归纳假设在这里成立，因为ds =0=路(s，s)和dv =路(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

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