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