dijkstra's negative weight yr ans required

Question

Which of the following statements is NOT true?

• A. Adding a constant to every edge weight in a directed graph can change the set of edges that belongs to shortest path tree. Assume unique weights
  
• B. Adding a constant to every edge weight in an undirected graph can change the set of edges that belongs to the minimum spanning tree
  
• C. Rerunning Dijkstra's algorithm on a graph $V$ times will result in the correct shortest paths tree, even if there are negative edges (but no negative cycles)
  
• D. None of these

Answer 1

B is correct. Draw some graph and visualize.
C is wrong. Dijkstra will work fine for -ve edge weight when we eliminate a vertex after using the vertex 2 times.

Comments

http://stackoverflow.com/questions/28587924/dijkstras-algorithms-and-negative-weights-and-cycle

i think ans is d, hv u any exa for option 1 and 2????

Answer 2

the answer should be none . as both 1 and 2 are true. it doesn't matter the graph is directed or undirected., the minimum cost spanning tree will not change by adding constants till the weights are kept unique. while dijisktra gives the right answer if made to run on a graph with no negative cycle. so c is true. 1 and 2 are wrong

Comments

option 3 is false if graph contain negative edge but not negative weight cycle then also dijkstras algo may gives wrong answer. http://stackoverflow.com/questions/28587924/dijkstras-algorithms-and-negative-weights-and-cycle