Least Cost Path Discovery over Graphs Defined for Large Volumes of Data Satisfying Node and Link Constraints
Shom C.Abraham · International Journal of Computer Applications · 2013
Computing shortest paths in graphs is one of the most fundamental and well-studied problems in combinatorial optimization.Numerous real-world applications have stimulated research investigations in this area.Several applications include large graphs involving thousands of nodes, which we cannot assume to be fully loaded into memory.The problem is of much interest, when the nodes and edges have several constraints to be satisfied apart from being large, in the computation of shortest path.Conventional Dijkstra's algorithm does not serve the purpose.There has not been much research done in this area, although some papers investigate the problem of large graphs.The problem of finding an efficient point-to-point shortest path algorithm for graphs of larger sizes, satisfying node as well as link constraints is solved using two optimization strategies.First, we implement bi-directional Dijkstra's algorithm with priority queue implementation using the heuristic value, in the path finding.The bi-directional strategy reduces the search space.Second, we introduce index of the graph table to preserve the local shortest segments, and exploit the table to further improve the performance.The final experimental results illustrates that this novel approach with the optimization strategies achieves high scalability and performance.