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 Nn-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