拆边法求最短路径

• 作者: 舒兴明
• 来源期刊: 海南师范学院学报(自然科学版)
• 学科: 数学
• 关键词: 最短路径问题 无向图 子图 可去边 拆边法
• 年，卷（期）: 2001,（4）
• 页码范围: 16-19
• 页数: 4页
• 分类号: O157
• 字数: 2187字
• 语种: 中文
• DOI: 10.3969/j.issn.1674-4942.2001.04.003

摘要

对于给定赋权的一个无向图,给出子图、无效路径以及可去边的定义,并在推导出有关定理的基础上,举例说明用拆边法求最短路径的方法:先利用局部比较法在图中拆去可去边,再利用最短路径相同的等价性对图化简,从而求出最短路径.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	舒兴明	华南热带农业大学经贸学院	10	20	2.0	4.0