Return to Index
Operations Research Models and Methods
Computation Section
Subunit Optimize
 -Path Tree

As for the spanning tree problems, we assign a length to each arc of a directed complete graph. For the path problem, the goal is to select a spanning tree so that the length of the path to each node is minimized or maximized. For an example, the length of an arc might represent the travel time for a vehicle. Emergency vehicles are located at the root node and we wish to find a travel path from the root node to a specified destination that has the smallest total travel time. In fact we want to find set of paths from the root node to all other nodes such that the length of each path is minimized for its destination. It is not hard to show that there will be an optimum solution such that the arcs in the collection will form a spanning tree.

With the Optimize add-in all the computations are very general. The Combinatorics add-in provides a less general but more efficient treatment of the path tree.

To illustrate we construct a combinatorial form for a network with 7 nodes.

  An example is shown below with random data. Rather than the tree with all arcs originating at node 1, we have chosen the initial tree shown below. The arc lengths are in parentheses and the path length to a node is in square brackets.


On the combinatorial form the tree is defined by the variables in row 7. Row 8 uses the Excel Index function to return the lengths of the tree arcs. Row 9 contains Excel equations that compute the path lengths to the nodes that correspond to the numbers in the brackets on the graph. Cell D3 computes the sum of the path lengths. It is the goal of the optimization to find the spanning tree that minimizes the value of the objective in D3. The solution will also minimize the length of the path to any individual node.


Those familiar with this type of problem will recognize that we have described the shortest path tree problem. There are many algorithms to solve this problem. For the symmetric problem there is a greedy approach that yields the optimum solution. The asymmetric problem with nonnegative arc lengths has a linear programming formulation and can be solved by the simplex method. Here we use combinatorial methods.

Solving the problem with exhaustive enumeration involves the evaluation of the same number of solutions as the maximal spanning tree problem. The best 20 solutions are shown below. Note that an alternative optimum is shown at the top. The second line shows the final run that repeats the optimum discovered in run 3434.


The optimum solution is pictured below.

The form showing the optimum is below.


Greedy Solution and Heuristics


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.

Return to Top

tree roots

Operations Research Models and Methods
by Paul A. Jensen
Copyright 2004 - All rights reserved