42
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Here is my example to a similar question which proves that the minimum spanning tree is not same with a shortest path. cs.stackexchange.com/a/43327/34363 $\endgroup$ – atayenel Jun 8 '15 at 0:50
  • $\begingroup$ Also, this might be interesting. Maximum spanning tree has paths between nodes where each path is a bottleneck path i.e. instead of minimizing the sum you maximize the minimum weight. Maybe there is a similar relation between minimum spanning tree. $\endgroup$ – Eugene May 25 '17 at 19:44
35
$\begingroup$

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.

$\endgroup$
29
$\begingroup$

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).

trees: Dijkstra vs Kruskal

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.

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

I think an example will make it clearer..

enter image description here

In this graph the minimum spanning tree is a cross-like shape with node 2 in the center. This is because that clearly gives the least total cost: 2+5+14+4=25.

What you might notice is that, this doesn't mean that the spanning tree is the most cost-efficient path between two nodes (even if that happens to be in many cases). For example going from node 1 to 4 could be done with a cost of 5 in Dijkstra's algorithm (the nodes are next to each other!). However with the minimum spanning tree they are forced to go through node 2 yielding a cost of 7.

$\endgroup$
-1
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ Welcome to the site. I don't think your analogy is a good one, since the route taken by a bus doesn't seem to have much to do with spanning trees. In particular, it's not spanning (it doesn't visit every point in the town) and it's not a tree. Rather, it's some kind of path (or cycle) that visits or passes close to as many significant points as is reasonable, so that the route is reasonably useful to a reasonably large number of people. $\endgroup$ – David Richerby May 25 '17 at 15:49
-1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.