Shortest Path Algorithm for Hypergraphs
CSTR:
Author:
Affiliation:

Clc Number:

O157.5

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    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)).

    Reference
    Related
    Cited by
Get Citation

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

Copy
Related Videos

Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:June 23,2005
  • Revised:June 23,2005
  • Adopted:
  • Online:
  • Published:
Article QR Code