Two Improved Shortest Path Algorithms And Their Applications

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 (minimum spanning tree), then we can choose the one and only path in the MST and it just the path what we want. However, there is a lack of providing any idea on both the optimization methods in one algorithm. Based on the method from Dijkstra algorithm to increase by degrees in the path-constructing, we present the MSPT(min-maximal weight shortest path tree) algorithm and the SMPT (shortest min-maximal weight path tree) algorithm. We prefer the shortest path to the min-maximal weight path in the MSPT algorithm, and prefer the min-maximal weight path to the shortest path in the SMPT algorithm. Both of them keep the same complexity to the Dijkstra algorithm, but add a transverse optimization to it. At the same time, we give an applied model so that we can choose one from them due to our different requirements.