In the minimum spanning tree problem, the connection of different nodes of a network is given. The goal is to obtain a tree whose sum of distances is minimal. In lesson 7 of the Optimization City group, the subject of minimum spanning tree is taught with numerous examples.
Some examples of the application of this problem are:
- A construction company wants to use the least amount of cable for supplying electricity of that building.
- A company is looking for a route that minimizes the length of the road to connect between the villages of a region.
- The Water and Sewerage Department intends to use the shortest length of pipe to create a water supply network in a town.
There is no specific software to solve this problem. Also, due to the huge application of the minimum spanning tree, the need for an efficient solver for this problem is very necessary. Optimization City group has designed and implemented an online solution for the minimum spanning tree. In the following, we will review how to use this online solver.
Instruction of using online solver of the minimum spanning tree
The GUI of the online solver of this problem is as follows.
To find the optimal solution of the minimum spanning tree problem, the required entries are as follows:
n: the number of nodes in the graph.
dist: is the graph cost matrix, which is a matrix with n+1 rows and n+1 columns.
Example: To teach how to use this solver, we use the following example. A weighted graph is given below. Get the minimum spanning tree.
Solution: The input information for the given graph is as follows.
Entering information in the online solver of the minimum spanning tree is as follows. Note that leave a comma between each entry to separate the numbers. For edges that do not exist in the graph, we consider the weight of 99.
After entering the data, we click on the RUN button.
The result of running the algorithm is as follows.
In the output of the algorithm, each row represents an edge that exists in the minimum spanning tree. The first number indicates the vertex of the beginning of the edge and the second number indicates the vertex of the end of the edge.