¹School of Computer Science & Engineering, Chongqing Three Gorges University, Chongqing, China.
²Web Sciences Center, University of Electronic Science & Technologhy of China, Chengdu, China.

---

Abstract—In order to search the shortest path from hypergraphs with unweighted hyperedges, a kind of searching algorithm based on the width-first strategy is presented at first. For hypergraphs with weighted hyperedges, a kind of searching algorithm based on the minimum-cost-first strategy to search the shortest path is presented. In order to enhance the reliability of the two algorithms, their correctness is proven in theory. The ideas and outlines of the two algorithms are illuminated by using two examples. Through the simulation of some artificial hypergraphs, the two algorithms are compared in time cost and the average percentage between the number of nodes in branching trees and the number of all nodes. We find that they can get the same average percentage. This result is consistent with the actual instance. In the end, it gives a research expectation to disinter and popularize the two algorithms.

Index Terms—Hypergraph, minimum-cost-first, shortest path, width-first.

[PDF]

Cite: Xinquan Chen, "The Shortest Path Algorithms of Hypergraphs Based on Search Strategies," Journal of Software vol. 10, no. 1, pp. 94-105, 2015.