Operations Management - Network Problems
Minimum spanning tree algorithm
Posted On :
Tree: A minimally connected network is called a tree. If there are n nodes in a network, it will be a tree if the number of edges = n-1.
Minimum spanning tree
algorithm
Problem : Given a connected network with weights assigned to the edges, it is required to find out a tree whose nodes are the same as those of the network.
The weight assigned to an edge may be regarded as the distance between the two nodes with which the edge is incident.
The problem can be solved with the help of the following algorithm.
The procedure consists of selection of a node at each step.
Step 1
First select any node in the network. This can be done arbitrarily.
We will start with this node.
Step 2
Connect the selected node to the nearest node.
Step 3
Consider the nodes that are now connected. Consider the remaining nodes. If there is no node remaining, then stop. On the other hand, if some nodes remain, among them find out which one is nearest to the nodes that are already connected. Select this node and go to Step 2.
Thus the method involves the repeated application of Steps 2 and 3. Since the number of nodes in the given network is finite, the process will end after a finite number of steps. The algorithm will terminate with step 3.
While applying the above algorithm, if some nodes remain in step 3 and if there is a tie in the nearest node, then the tie can be broken arbitrarily.
As a consequence of tie, we may end up with more than one optimal solution.
Problem : Given a connected network with weights assigned to the edges, it is required to find out a tree whose nodes are the same as those of the network.
The weight assigned to an edge may be regarded as the distance between the two nodes with which the edge is incident.
Algorithm
The problem can be solved with the help of the following algorithm.
The procedure consists of selection of a node at each step.
First select any node in the network. This can be done arbitrarily.
We will start with this node.
Step 2
Connect the selected node to the nearest node.
Step 3
Consider the nodes that are now connected. Consider the remaining nodes. If there is no node remaining, then stop. On the other hand, if some nodes remain, among them find out which one is nearest to the nodes that are already connected. Select this node and go to Step 2.
Thus the method involves the repeated application of Steps 2 and 3. Since the number of nodes in the given network is finite, the process will end after a finite number of steps. The algorithm will terminate with step 3.
How to break ties
While applying the above algorithm, if some nodes remain in step 3 and if there is a tie in the nearest node, then the tie can be broken arbitrarily.
As a consequence of tie, we may end up with more than one optimal solution.
Tags : Operations Management - Network Problems
Last 30 days 619 views
