edited by
1,362 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 ?)
edited by

2 Answers

Best answer
1 votes
1 votes

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

0 votes
0 votes
0 answers
3
0 votes
0 votes
0 answers
4
CHïntän ÞäTël asked Dec 25, 2018
342 views
According To Me Answer Should Be 6… Anyone Please Try Once!!! Given Is 5 With No Explaination !!!!like 11-12-12 then for second square 4 times 13 so c(4,2) any two of t...