Meliorated Approach for Efficient Computation of Shortest Path on Edge Based Data Structure
Anand Kumar Gupta, Ankur Maheshwari, Gaurav Jain · 2009
The novel representation of the graph using edge based data structure, as proposed in [1] is an adapted version of half edge structure, traditionally used in digital geometry processing [6]. This edge based data structure provides an efficient way for storing and accessing graphs. However the shortest path algorithm implemented in [1] on the above mentioned data structure proves to be inefficient when dealing with extensive graphs with varying scales and degrees. The main concern is to minimize the time and space overheads involved, as they take a great toll on system resources. The short comings associated with the above mentioned approach acted as our motivation. In this paper, we present an approach based on greedy and intuitionist programming strategies, which derives advantages from heuristics that apply to all kinds of graph, hence achieving greater efficiency. This aspect of the algorithm is also borne out by the experimental conclusions we have obtained.