一类树图的最短路的算法

ALGORITHM ON SOME SHORTEST PATH OF DENDROGRAM

本文研究了边点赋权图、顶点关于图的运输量及质心,利用比较两个相邻顶点的运输量的方法,得到了一个连通树图的顶点是质心的充要条件及质心个数不大于2的结果.同时给出了求质心及最小运输量的算法,其算法的时间复杂度为O(n2),有利于可建立树图模型的优化问题的求解.

In this paper, the edge and vertex weighted graph, the transportation capacity of vertex to the graph and centroid of the graph are introduced and studied. By comparing transportation capacity of two adjacent vertices, it obtains that a necessity and sufficiency condition is that a vertex of a graph is centroid and the number of the centroids of a graph is not greater than 2. In addition, the algorithm on finding the centroid and the minimal transportation capacity are derived, of whih its complexity is O（n2）. It is conducive to solve the optimization problem, which can be made by dendrogram.