The problem with nonnegative and
symmetric arc lengths can be solved by *Dijksta's**
algorithm *described elsewhere on this site. This is a greedy
approach that constructs a solution by starting from the root
node and adding the arc with the smallest length to obtain a
tree with two nodes. The algorithm then procedes by extending
the tree to an additional node such that the length of the path
to the node passing only through nodes already in the tree is
minimized. The process continues until *n*-1 arcs are
selected and all nodes are connected. When the arc lengths are
nonnegative and not symmetric, this method yields a tree that
is not necessarily optimum. Although not symmetric, the greedy
algorithm does reach the optimum for the example.
We illustrate the improvement process by starting
from the solution given at the top of this page (the nodes visted
in numerical order). The results are below. The initial solution
is at the bottom of the list and subsequent improved solutions
appear above it. The improvement approach is the same as for
the spanning tree. Each nontree arc is inserted in the tree
and the current solution arc terminating at the same node as
the entering arc is deleted. If a cycle is not formed, the solution
is evaluated. An improved solution replaces the current incumbent.
The improvement process we have described is equivalent
to the steps that would be taken by the primal simplex method
using a similar rule for selecting the variable to enter the
basis. The improvement process will in fact always yield the
optimum for the linear path problem, so it is never necessary
to perform exhaustive enumeration or make random searches.
For the linear path problem with nonnegative costs,
the greedy approach yields the optimum for symmetric problems
and the improvement approach applied to an arbitrary initial
tree yields the optimum for asymmetric problems. A time consumming
combinatorial approach is only necessary if the problem is complicated
in some way by adding constraints on feasibility or making the
problem nonlinear. The latter is illustrated on the next page. |