关键词: 图论 最小生成树 最短路径 最大权值最小路径 Dijkstra算法 缺货风险

Abstract:

There are two basic optimization methods, the shortest path and the min-maximal weight path. The solution to the former is the famous Dijkstra Algorit  hm, 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 o f 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 pa  th-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 i  t is more suitable for practical requirements.Meanwhile, we give an applied model.

Key words: graph theory;the minimum spanning tree;the shortest path;the min-maximal weight path;D ijkstra algorithm;risk out of stock.