MadeEasy Subject Test: Algorithms - Graph Algorithms

Question

Which of the following statements is true?

• Adding a constant to every edge weight in a directed graph can change the set of edges that belongs to minimum cost spanning tree. Assume unique weights.
• Complete graph with 4 vertices, each edges having same weights can have maximum 28 minimum cost spanning tree.
• 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).
• None of these

how is 3rd wrong? If there is no negative cycles dijkstra can work just fine right?

Comments

@ S Ram...if there are negative weight cycles than dijkstra will surely fail but if there are negative weight edges(need not be cycle) then dijkstra may or may not fail.

Answer 1

No. Dijkstra may give incorrect result if negative edges are present.

Then we use Bellman-Ford, and it may fail in case of negative edge weight cycles.