Operations Research Models and Methods / Methods / Network
||Unit 1: Minimal Spanning Tree and Shortest
Path Tree 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.
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
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.
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 figures show 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
Operations Research Models and Methods
by Paul A. Jensen and Jon Bard, University of Texas, Copyright
by the Authors