Shortest path tree claim (Graph)
Claim: If all the edges weights in a graph are distinct, then there is a unique shortest path tree. Either give a convincing argument that the claim is true or give a counterexample.
If you have MST then there is a unique path from every two vertices which makes the shortest path tree senseless. I assume you meant the result is a MST. However, this is not true. Shortest path trees are different from minimum spanning trees for the same graph and even for the same root. Shortest Path tree rooted on vertex v is usually the result of applying Dijkstra's algorithm over v.
In general, uniqueness for trees over graphs is hard to be believed in unless strict requirements were given (like the new weights equal old ones +1). @rici gave a counterexample with a polytree structure. Here is another counterexample for undirected graphs. Both trees are shortest path trees rooted at A. Note that:
- While both are shortest path trees, their total cost differ.
- Both are spanning trees but neither one of them is a minimum.
