in Algorithms edited by
883 views
2 votes
2 votes
(1). Both BFS and DFS require $\Omega (N)$ storage for their operation.

(2). If we double the weight of every edge in the Graph shortest path between any two vertices will not change.

Which of the following is/are True ?

(and in every question of shortest path we have to think about negative weight ?)
in Algorithms edited by
by
883 views

4 Comments

only $1$ will be true
0
0
Omega represents the lower bound or best case, so why do you think that DFS or BFS in worst case will take omega(N) space ?, what I think is they will take O(N) in even Worst case.
0
0
$\Omega (n) \text{means that you storage capacity have to have atleast n}$

It is correct.how can you keep track of visited node having array size less than its size i.e $n$?

Are there  other optimization possible?
0
0
Can anyone please explain how statement 2 is incorrect ?

I agree that a constant addition may change the path,

But a constant ratio always gives the same path.

consider the shortest path between two edges be a+b+c and another path between them as w+x+y+z.

Now if a+b+c < w+x+y+z

Then by simple inequality ratio we can deduce that

2a+2b+2c < 2w+2x+2y+2z

How can you prove its inverse ?

Statement 2 is correct.
0
0

2 Answers

1 vote
1 vote
Best answer

(1) BFS and DFS both stores every node of the graph. So, storage location must be same for both of them

(2) is  true always

take this graph for example. Shortest path will not change when u double every edge weight

After a lot of example checking, I concluded that, if we double an edge or we break that edge in some part, and then double each part, shortest path will not change.

selected by

4 Comments

@ Mr_22B

u can chk here, it doesnot matter in bfs or dfs

https://gateoverflow.in/405/gate2008-7

Still if u have doubt , u can ask

1
1
Thank you.
0
0
@srestha

For statement 1: Omega means best case ( f >= g )

But in best case, BFS takes omega (n) and for DFS best case is omega( log n).

How 2nd is always true? What if I take the weight as negative? (nothing is mentioned in question )
0
0
0 votes
0 votes
Basically BFS uses Queue for storing and DFS uses Stack for storing its unexplored nodes.

So in case of BFS storage must be O(N) and Ω(N)

But in DFS stack depends on height of the tree hence in best case i.e lowest bound complexity should be  Ω(LogN) and in worst case it will be O(N)

Hence option 1 is false

Option 2 is correct

Related questions