BFS分析

Question

我有来自Cormen的以下BFS功能.

将从s到v的最短路径距离路径(s,v)定义为从顶点s到顶点v的任何路径中的最小边数,否则如果没有从s到v的路径.长度路径的路径(s,v)从s到v被认为是从s到v的最短路径.

以下是给出的引理

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

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

我的问题是为什么我们必须<=在上面的公式,我教"="是好的,任何人都可以告诉我一个scenrio为什么我们要求<=？

下面是BFS算法

利马2:

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

证明:

我们对顶点放入队列Q的次数使用归纳法.我们的归纳假设是d [v]> =所有v的路径(s,v)属于V.

诱导的基础是在BFS的第8行中将s置于Q之后的情况.

归纳假设在这里成立,因为d [s] = 0 =路径(s,s)和d [v] =所有v的路径(s,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是真的吗？