一个改进的调配算法

摘要

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