两类网络连接问题中的最小费用算法及其应用

Minimum Cost Algorithm and Its Application in Two Types of Network Connection

利用MergeSort算法对加权图中任意两点之间的权值进行排序,把这些权值从小到大进行排列放在一个队列,再利用Kruskal算法求该队列的最小生成树,并将该方法运用于城市交通网络的费用计算;而对于供水管道铺设的最小费用问题可通过最小树形图算法来解决。

Using the MergeSort algorithm, weights between any two points in weighted graph is ordered in this paper. Firstly, the weights from small to large in a quene is ranked. Then by using Kruskal algorithm for seeking the minimum spanning tree in this queue, we can apply this method to work out the cost of Urban transportation network. It can be solved by minimal tree algorithm to minimize cost of laying water supply pipes.