Minimum spanning tree vs Shortest path

Question

What is the difference between minimum spanning tree algorithm and a shortest path algorithm?

In my data structures class we covered two minimum spanning tree algorithms (Prim's and Kruskal's) and one shortest path algorithm (Dijkstra's).

Minimum spanning tree is a tree in a graph that spans all the vertices and total weight of a tree is minimal. Shortest path is quite obvious, it is a shortest path from one vertex to another.

What I don't understand is since minimum spanning tree has a minimal total weight, wouldn't the paths in the tree be the shortest paths? Can anybody explain what I'm missing?

Any help is appreciated.

Answer 1

You are right that the two algorithms of Dijkstra (shortest paths from a single start node) and Prim (minimal weight spanning tree starting from a given node) have a very similar structure. They are both greedy (take the best edge from the present point of view) and build a tree spanning the graph.

The value they minimize however is different. Dijkstra selects as next edge the one that leads out from the tree to a node not yet chosen closest to the starting node. (Then with this choice, distances are recalculated.) Prim choses as edge the shortest one leading out of the tree constructed so far. So, both algorithms chose a "minimal edge". The main difference is the value chosen to be minimal. For Dijkstra it is the length of the complete path from start node to the candidate node, for Prim it is just the weight of that single edge.

To see the difference you should try to construct a few examples to see what happens, That is really instructive. The simplest example that shows different behaviour is a triangle $x,y,z$ with edges $\{x,y\}$ and $\{x,z\}$ of length 2, while $\{y,z\}$ has length 1. Starting in $x$ Dijkstra will choose $\{x,y\}$ and $\{x,z\}$ (giving two paths of length 2) while Prim chooses $\{x,y\}$ and $\{y,z\}$ (giving spanning tree of weight 3).

As for Kruskal, that is slightly different. It solves the minimal spanning tree, but during execution it chooses edge that may not form a tree, they just avoid cycles. So the partial solutions may be disconnected. In the end you get a tree.

Answer 2

Consider the triangle graph with unit weights - it has three vertices $x,y,z$, and all three edges $\{x,y\},\{x,z\},\{y,z\}$ have weight $1$. The shortest path between any two vertices is the direct path, but if you put all of them together you get a triangle rather than a tree. Every collection of two edges forms a minimum spanning tree in this graph, yet if (for example) you choose $\{x,y\},\{y,z\}$, then you miss the shortest path $\{x,z\}$.

In conclusion, if you put all shortest paths together, you don't necessarily get a tree.

Answer 3

Though Minimum Spanning Tree and Shortest Path algorithms computation looks similar they focus on 2 different requirements.

In MST, requirement is to reach each vertex once (create graph tree) and total (collective) cost of reaching each vertex is required to be minimum among all possible combinations.

In Shortest Path, requirement is to reach destination vertex from source vertex with lowest possible cost (shortest weight). So here we do not worry about reaching each vertex instead only focus on source and destination vertices and thats where lies the difference.

Here is the example to clarify why MST not necessarily gives shortest path between 2 vertices.

(A)----5---(B)----5---(C)
 |                     |
 |----------7----------| 

In MST case, edges A-B. B-C will be on MST with total weight of 10. So cost of reaching A to C in MST is 10.

But in Shortest Path case, shortest path between A to C is A-C which is 7. A-C was never on MST.

Answer 4

I think an example will make it clearer..

The spanning tree looks like below. This is because if we add up the edges in this configuration, we get the least total cost possible: 2+5+14+4=25.

(1)   (4)
  \   /
   (2)
  /   \
(3)   (5)

By eyeballing the spanning tree you might falsely think that it gives you the shortest paths, but in practice it doesn't. As an example If we wanted to go from node (1) to (4) it would cost us 7. However if we used Dijkstra's algorithm on the original graph, we would find that we can go directly from node (1) to (4) with a cost of 5.

Answer 5

The difference lies in what is the ultimate goal of this algorithms-

Dijkstra's - Here the goal is to reach from start to end. You are concerned about only this 2 points, and optimize your path accordingly.

Krusal's - Here you can start from any point and have to visit all other points in the graph. So, you may not always choose the shortest path for any two points. Instead the focus is to choose the path that will lead you to a shorter path for all the other points.

Answer 6

The key is to understand that they are different problems: The spanning tree looks to visit all nodes in one "tour", while shortest paths focuses on the the shortest path to one node at a time.

As an example, imagine you know the shortest route from your home to two different places A and B. Since the graph is directed, you can get to B from A but not vice versa. In this case, the route Home -> B is shorter than Home -> A -> B, so you're allowed to skip A. But for spanning trees, you must visit all nodes, so Home -> A -> B is the solution (Assuming that Home -> B -> A is more expensive than Home -> A -> B.

Answer 7

Consider a simple example You are building a food delivery app, You want the driver to deliver food to all customers by covering the distance in optimal way with minimum possible time and fuel If you want to cover all the locations, you need minimum spanning tree. If you are targeting only a single location, you need the shortest path.

The shortest path will not guarantee covering all the vertices ( reaching to all the customers in the above example ). To cover all the customers, you have to find minimal spanning tree.

Answer 8

I think minimum spanning tree algorithm aims to extract a tree whose overall cost is minimized and it doesn't care about the minimum distance from a single node to the starting node, which is exactly what shortest path aims at. And that's why Prim colors the node which has minimum distance to any one of the colored nodes, while Dijkstra colors the node with minimum distance to the starting node.

Answer 9

They are based on two different properties. Minimum spanning tree is based on cut property whereas Shortest path is based on the edge relaxing property.

A cut splits a graph into two components. It may involve multiple edges. In MST, we select the edge with the least weight.

Edge relaxing says that given I know distance between A and B: dist(a,b) and dist between A and C: dist(a, c), if dist(a, b) + edge(b, c) is less than dist (a, c), then I can relax edge(a c). After relaxing all edges, we get the shortest path.

I highly recommend watching the video on graph algorithms from professor Robert Sedgewick.

Answer 10

Practical example to show the difference>

Suppose you arrive by train in a town and want to get to your hotel.

Option 1: Get a taxi: The taxi will take the shortest path to you hotel form the station. If the driver should follow a path along the shortest path tree centred on the station.

Option 2: Take a bus. The bus company wants to cater for may people, not just you. The ideal path would take in all the key points in the town. So it will follow (*) a path along the minimum spanning tree. That's why the bus is slower, but as costs are shared it is cheaper.

(*) Actually people would complain if the minimum spanning tree was used (the bus journey would be too long). So in practice it would be a mixed solution and would use an Alpha-Tree (half way between a minimum spanning tree and a shortest path tree).