Made easy test series

Question

In this question why option C is correct and option B is wrong?

Comments

I tried and cannot see why it is wrong. If you got it , do share please.

---

$w=-10$ creates a negative cycle.

Consider the cycle: $b→c→d→a→b$

Total cycle weight: $w + 1 + 3 + 2 = w + 6$

If $w=-10 ⇒ cycle$ $weight=−10+6=−4$

That is a negative cycle.

And if,
$w=-1 ⇒ cycle$ $weight=−1+6=5$

So, here:

• There is a negative edge

• But no negative-weight cycle
   

Hence, Option B is incorrect and Option C is correct.

---

hey, thanks @Hetul_Mehta for the explanation. 

I have a doubt.

Consider this path S->a->b->c->b and w = -1.

Since it is a undirected graph I can go back to b from c.

Now because b-c edge is already relaxed, c goes back to b and reduces the weight on b this is wrong dijkstra path.

If you run properly then weight on b = 3 (S->a->b). when I add w = -1 (b->c->b) then weight on b = 2.

Let me know where I am doing mistake.

---

Thanks for the responses,
Since the graph is undirected, I believe even w = -1 could create a negative cycle like : b -> c -> b : weight = -1 + -1 = -2.
So I do not really see @Hetul_Mehta your response could solve the issue.