求所有最小点成本最短路径算法

• 作者: 何建军 王丽芳
• 来源期刊: 软件导刊
• 学科: 工学
• 关键词: 最短路径 点带成本 带权图 最小点成本最短路径
• 年，卷（期）: 2015,（4）
• 所属期刊栏目: 算法与语言
• 页码范围: 78-80
• 页数: 3页
• 分类号: TP312
• 字数: 3005字
• 语种: 中文
• DOI: 10.11907/rjdk.1431088

摘要

对点带成本的最短路径问题进行了研究。根据点带成本最短路径问题特点，对Dijkstra算法进行修改后给出一个时间复杂度为O（｜V｜2＋｜E｜）、空间复杂度为O（｜V｜＋｜E｜）的算法，并在此基础上充分利用问题的特点，给出一个时间复杂度为O （w｜V｜）、空间复杂度为O （｜V｜＋｜E｜）、构造所有点带成本最短路径的算法。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	何建军	重庆大学城市科技学院	10	267	6.0	10.0
2	王丽芳	重庆大学城市科技学院	18	15	2.0	2.0