一个改进的调配算法

An Advanced Algorithm for Scheduling

图中路径的基本优化策略有两种最短路径和最大权值最小路径。前者的求解有著名的Dijkstra算法;后者的求解通过先构造图的最小生成树MST,再截取其上两端点间的唯一路径就是最大权值最小路径。但是,尚未有文献提出算法同时争取两方面的优化。本文采用Dijkstra算法构造路径时不断递增的基本思想,提出MSPT算法。MSPT算法是在求得最短路径的同时最大限度地争取最大权值最小。其算法时间复杂度和空间复杂度均与Dijkstra算法相同,但比Dijkstra算法横向上增加了一层优化,更切合实际问题的需要。同时,该文给出了MSPT算法的实际应用模型。

There are two basic optimization methods, the shortest path and the min-maximal weight path. The solution to the former is the famous Dijkstra Algorithm, and the latter is to construct a MST,then we can choose the one and only path in the MST and it is just the path we want. However, there is a lack of providing any idea on both the optimization methods in one algorithm. Based on the method from the Dijkstra algorithm to increase by degrees in the path-construction, we supply the MSPT（min-maximal weight shortest path tree） algorithm. We strive for an almost min-maximal weight path on the basis of the shortest path in the MSPT algorithm. And it keeps the same complexity to the Dijkstra algorithm, but adds a transverse optimization to it so that it is more suitable for practical requirements.Meanwhile, we give an applied model.