超图的最短路径算法
中图分类号:

O157.5


Shortest Path Algorithm for Hypergraphs
  • 摘要
  • | |
  • 访问统计
  • | |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

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

    Abstract:

    Based on strong isomorphism for hypergraphs,vertex isomorphism is defined,which preserves hyper-adjacency property between vertices.Adjacency-matrixes of hypergraphs and weighted hypergraphs are presented respectively.The Floyd's algorithm is generalized to finding shortest paths between all pairs of vertices in a hypergraph.The publication provides an instance which verifies the practicability of the modified algorithm and whose results have been compared with those of the method given by LI Chun-ming.Time complexity of the presented algorithm is obtained to be(O(n~3)).

    参考文献
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

龚劬,程绩.超图的最短路径算法[J].重庆大学学报,2005,28(11):106-109.

复制
分享
文章指标
  • 点击次数:696
  • 下载次数: 189
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2005-06-23
  • 最后修改日期:2005-06-23
文章二维码