一个改进的调配算法

• 作者: 刘建伟 卢建朱 张彦军
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: 图论 最小生成树 最短路径 最大权值最小路径 Dijkstra算法 缺货风险
• 年，卷（期）: 2007,（1）
• 所属期刊栏目: 算法研究
• 页码范围: 73-75
• 页数: 3页
• 分类号: TP301.6
• 字数: 2970字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2007.01.023

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘建伟	暨南大学信息科学技术学院	22	167	7.0	12.0
2	张彦军	暨南大学信息科学技术学院	11	29	4.0	5.0
3	卢建朱	暨南大学信息科学技术学院	41	339	10.0	17.0