only $1$ will be true

Dark Mode

883 views

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 ?)

(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 ?)

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.

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

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.

@ 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

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

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