超图的最短路径算法

被引：8

作者：

龚劬

程绩

机构：

[1] 重庆大学数理学院

[2] 重庆大学数理学院重庆

[3] 重庆

来源：

关键词：

超图; 点同构; 邻接矩阵; Floyd算法;

D O I：

暂无

中图分类号：

O157.5 [图论];

学科分类号：

070104 ;

摘要：

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

引用

页码：110 / 113

页数：4