超图的最短路径算法

• 作者: 程绩 龚劬
• 来源期刊: 重庆大学学报（自然科学版）
• 学科: 数学
• 关键词: 超图 点同构 邻接矩阵 Floyd算法
• 年，卷（期）: 2005,（11）
• 所属期刊栏目: 电气·热能·材料工程·数学·物理
• 页码范围: 106-109
• 页数: 4页
• 分类号: O157.5
• 字数: 4493字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-582X.2005.11.028

摘要

从超图的强同构引出保持超图顶点间超邻接性的点同构,定义超图的邻接矩阵和赋权超图的权矩阵,并在此基础上得到了求解超图任意顶点间最短路径和求解超图直径的推广Floyd算法.最后通过实例验证了算法的可行性,并与李春明在1994年得到的结果进行比较,得出算法的复杂度为O(n3),该算法是一个有效算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	龚劬	重庆大学数理学院	60	392	12.0	16.0
2	程绩	重庆大学数理学院	2	18	2.0	2.0