CODEWITHSUNDEEP
algorithmbreadth-first-search
venkysmarty
venkysmarty

Reputation: 11441

Analysis of BFS

I have the following BFS function from Cormen.

Definition of the shortest-path distance path(s,v) from s to v as the minimum number of edges in any path from vertex s to vertex v, or else if there is no path from s to v. A path of length path(s,v) from s to v is said to be a shortest path from s to v.

Following is lemma given

Let G = (V,E) be a directed or undirected graph, and let s belongs to V be an arbitrary vertex. Then, for any edge (u, v) E,

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

My question is why we have to have <= in above formula, i taught "=" is ok, can any one tell me one scenrio why we require <= ?

Below is BFS algorithm

Leema 2:

Let G = (V,E) be a directed or undirected graph, and suppose that BFS is run on G from a given source vertex s belongs to V. Then upon termination, for each vertex v belongs to V, the value d[v] computed by BFS satisfies d[v] >= path (s, v).

Proof:

We use induction on the number of times a vertex is placed in the queue Q. Our inductive hypothesis is that d[v] >= path(s,v) for all v belongs to V.

The basis of the induction is the situation immediately after s is placed in Q in line 8 of BFS.

The inductive hypothesis holds here, because d[s] = 0 = path(s, s) and d[v] = path (s, v) for all v belongs to V - {s}.

My question is what does author mean by "We use induction on the number of times a vertex is placed in the queue Q" ? and how it is related to inductive hypothesis?

Thanks!

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

Upvotes: 0

Views: 640

Answers (1)

HexTree
HexTree

Reputation: 148

For your first question, consider a complete graph with only three vertices. In this graph is it true that path(s,v) = path(s,u) + 1 ?

Upvotes: 6

Related Questions