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

if there are negative weight cycles dijkstra will surely not work..but if there are negative weight edges(need not be cycle)..dijkstra may or may not work..

---

answer should be A

---

The statement 1 is true because adding a constant means adding different values of constant to all the edges then there is a chance of changing the set of edges in Minimum Spanning tree

 

Adding a constant is different from adding a constant value...I hope this explanation helps!!

Answer 1

S1: Wrong, because if the Edge weights are disticnt then adding a constant Value never changes the edgest in MST (though it may change the shortest path between two vertices)

S2: No of spanning tree of a complete graph of N vertices is N^n-2 here 4 =N so 16 . so WRONG

S3: WRONG 

Recall that in Dijkstra's algorithm, once a vertex is marked as "closed" (and out of the open set) - the algorithm found the shortest path to it, and will never have to develop this node again - it assumes the path developed to this path is the shortest. But with negative weights - it might not be true. For example: A / \ / \ / \ 5 2 / \ B--(-10)-->C V={A,B,C} ; E = {(A,C,2), (A,B,5), (B,C,-10)} Dijkstra from A will first develop C, and will later fail to find A->B->C

so None of them are correct here

NOTE: For Negative edge wight we use Bellman -Ford 

Comments

(A) is true. Consider this graph:

A-------7----------D

|                       |

|   1            3    |

B--------2----------C

If we increase the edge weights by 1, shortest path changes. First the shortest path from AtoD is 6( ABCD), but after adding 1, it changes to AD. 

Aren't I correct?

---

@Bongbirdie 1st statement is not about shortest path, statement is about set of edges belongs to MST

however you are right if its shortest path.

---

Madeeasy given statement 1 is correct, but it would be if it was shortest path.