Minimum Spanning Tree Algorithm - Revised

A network is defined by a set of nodes N and a set of arcs A.  In a compact form, the network is denoted by (N, A).  The nodes are depicted as circles with a number inside, which is used as a reference to the node and the order does not imply any preference or order.  The arcs are those lines that connect nodes with each other; and they are drawn with a  number on them that indicates a cost measure.

Networks can simplify many problems we face in operations research, and luckily, for almost all of them, we have methods and procedures to solve them.  One of these problems is the minimum spanning tree.

A tree is a network without cycles or loops, and the spanning tree is a tree that connects all the nodes of the network.  When a tree connects all the nodes with the smallest sum of the arc costs, the result will be the minimum spanning tree.

We present a labeling technique to find the minimum spanning tree for a network.  I have found that this labeling technique is easier for students taking an introductory course in operations research.  We will illustrate the technique by means of a real example on the establishment of an electricity network for the Kingdom of Saudi Arabia.

Electricity Network for the Kingdom

The Ministry of Water and Electricity has a plan to connect the major cities of the Kingdom with an interconnect electric power grid, so there will be central generator units located in Dhahran.  The generator units will run on natural gas, using the combined cycle technology.  The proposed network will be built out of high voltage power lines and city-gate transformers.  The distances between the cities in km are shown in the following map.

The connections shown in the map are all possible configuration of the network, when other factors, such as terrain, are considered.  Planners believe the cost of the construction of the network will be largely dependent on the length of the network; other components of the network can be treated as fixed costs, as they are essential parts of the electricity network.  Therefore, the total construction cost can be reduced if the length of the connections is reduced.  In view of this, the problem becomes of the construction of the minimum spanning tree and the minimum spanning tree algorithm can be used to find the cheapest configuration of the electric power network for the Kingdom.

Revised Minimum Spanning Tree Algorithm

The basic minimum spanning tree algorithm works by picking up the nodes of the network in succession.  In any stage of the algorithm, a tree is constructed that spans a subgroup of the nodes.  The algorithm terminates when all the nodes are connected to the spanning tree.  The steps of the algorithm can summarized as follows:

1. Choose any node in the network.

2. Locate the node closest (cheapest) to the selected node.

3. Locate the node closest to either one of the selected nodes, and repeat.

To effectively track the expansion of the tree, we propose a labeling procedure.  The labels establish the connections of nodes to each other.  The labeling procedure defines two kinds of labels: temporary and permanent.  Every node in the network has a label.  The label has two components:

[a, W]: a is the cost of connecting the node to the permanently labeled node W.

The first node has a permanent label [-, -].  The labeling procedure assign temporary labels to all nodes that can be connected to the permanently labeled nodes.  The label of the temporarily labeled node with the smallest cost component a is changed to permanent. After this, all temporary labels are updated and nodes are added, if any.  The steps of the labeling procedure are as follows:

1. Assign permanent label [-, -] to the selected node.

2. Locate all the nodes that have direct connection to the permanently labeled nodes, and assign to them temporary labels.

3. Find the label with the least cost component and change the status of the label to permanent.

4. If all nodes but one have permanent labels, stop.  Else, go to step 2.

Optimal Configuration of the Electric Power Grid for the Kingdom

We apply the labeling procedure to the design of the electric power grid for the Kingdom.  We can start from any node; as the solution will not be affected by the start node.  We choose node 1 to be the start node.  We can construct the following table:

Now, we add the nodes that can be connected to node 1, which is the only permanently labeled node:

Among all temporarily labeled nodes, the node that has the smallest cost will have a permanent label.  Since node 2 is the only temporality labeled node, its label is changed to permanent:

We add all the nodes that can be connected to the permanently labeled nodes:

The temporarily labeled node that has the smallest cost component is labeled permanent:

The following table will be:

The label of node 4 is changed to permanent.  The resulting table will be:

Node 8 can be connected to two permanently labeled nodes; 3 and 4.  The label with the higher cost should be removed.  The resulting table is:

Proceeding in this manner will produce the following table:

This will be the last table since all nodes except one have permanent labels.  From the labels, we can construct the minimum spanning tree.  Node 2 is connect to node 1, node 3 is connect to node 2, node 9 is connected to node 8, and so forth.  The minimum spanning tree looks like:

The total length of the network can be found by adding the cost part of the labels, which should be 3,310 km.