I can see that we can use Minimum spanning tree in Network design like telephone, electrical, hydraulic, TV cable, computer, road etc. But I am not quite clear that where exactly Shortest path tree can be used in real life, where MST algo will not be helpful.
1 Answers
As stated in this website, you would use a MST to "select a set of edges so that there is a path between each node. The sum of the edge lengths is to be minimized". And you would use a SPT to "find the set of edges connecting all nodes such that the sum of the edge lengths from the root to each node is minimized."
Basically MST focuses on the shortest path between all nodes, whereas a SPT focuses on the shortest path from root to every node.
In a real-world example, SPT is used in geographical maps, telephone networks, and usually in IP routing algorithms (basically when you need to reach each node from root with the smallest length).
Here is an example using an actual graph:
As you can see, a MST finds the minimum weight that connects all nodes, but a SPT finds the minimum weight when starting at a particular node.
In a real-world example where you would use a SPT instead of a MST would be for a hospital and the homes in its region. The goal is to find the shortest path starting from the hospital and to each individual home. That way in an emergency the ambulance could start at the hospital and reach any home with the smallest distance possible.
Related