Minimal Spanning Tree and Shortest PathTree Problems

We consider in this section two problems defined for an undirected graph. Since they are similar, the problems are often mistaken for one another. Both can be solved by greedy algorithms.

The Minimal Spanning Tree Problem

Consider the undirected network as shown in the figure. The graph consists of nodes and edges, and each edge has an associated length. An edge is the line segment connecting two nodes and has the same length in either direction.

The Minimal Spanning Tree problem is 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.

When the edge lengths are all nonnegative, as assumed here, the optimum selection of edges forms a spanning tree. Because of this characteristic of the solution, the problem is called the minimum spanning tree problem. The problem can be solved with a greedy algorithm called Prim's Algorithm. Click the link below to see the statement of the algorithm and a demonstration.

Prim's Algorithm

The algorithm is one of the simplest in optimization theory. The optimum is found after m ­1 performances of the selection step, where m is the number of nodes.

 

The Shortest Path Tree Problem

We consider again the same undirected graph, but now we solve a different problem. The graph consists of nodes and edges, and each edge has an associated length. In this problem we identify a root node and desire to find a path to each node from the root node such that the length of the path to each node is minimized.

The Shortest Path Tree problem is 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

Again assume all edge lengths are nonnegative. The optimum selection of edges forms a spanning tree. The problem can be solved with a greedy algorithm called Dijkstra's Algorithm. Click the link below to see the statement of the algorithm and a demonstration.

Dijkstra's Algorithm

The algorithm is adapted easily to directed networks with nonnegative arc lengths. The optimum is found after m ­1 performances of the selection step.

Comparing the Minimal Spanning Tree and Shortest Path Trees.

The figure shows the solutions to the minimal spanning tree and shortest path tree for the example problem. The solutions differ in their selection of edges, because the criteria for optimality for the two problems are different.

 Minimal Spanning Tree

Shortest Path Tree from Node 1

 

Return to Exercises Home Page

return to tour start