Algorithm questions on graphs

Question

Comments

B ) ???

Answer 1

The answer should be none of these as it depends on the values we take.

In both cases - it may or may not change the shortest path.

 

Consider this case between 0 and 2 - if we reduce by one, the path doesn't change. If we, however, reduce by six, the path changes.

Similarly, consider this graph:

For the same source and destination as before, if we add one to all the edges, the path doesn't change. If we add 10 to all the edges, the shortest path changes.

 

Comments

I am not understood the daigram one ..I think according to your explanation for 1st daigram reduced by one or four both the cases the path doesn't changes....

---

Oh right, it doesn't change by four. I've edited it to six, now the path should change. You can find similar counterexamples yourself.

---

Thank you