Questions on shortest path and minimum spanning tree T/F Questions


Adding a constant to every edge weight does not change the solution to the single-source shortest-paths problem. 
Solution - False


I think this should be True, as Dijkstra's Algorithm sums the paths from source to each vertex. If every edge weight is increased by a constant, then nothing should be changed if all edges are positive. If some edges are negatives, then I don't know if Dijkstra's Algorithm still applies here. 


Adding a constant to every edge weight does not change the solution to the MST problem. (I don't have the solution for this)


I think this is True for the same reason above. 

Can someone confirm on this?
You are wrong on the first one and right on the second one (but for the wrong reason). 

To see that (1) is false, just observe that there exists a constant $c$ such that adding $c$ to all weights turns the weighted minimum distance problem into the unweighted one.

On the other hand, (2) is true because every spanning tree contains has exactly $|V|-1$ edges, therefore adding $c$ to all weights adds $c(|V|-1)$ to the total cost of each spanning tree.