Improvement of shortest-path algorithms using subgraphs heuristics

Abstract

Given a graph G=(V,E,w), where V and E are finite set of vertices and edges respectively, is a directed weighted graph with weights denoted by w(e)>0 for each edge e ∈E. P(s,t) is the shortest path between the given vertices <s> and <t> containing the least sum of edge weights on the path from <s> to <t>. Properties of the graph representation, using different matrix structures to represent the graph in normal flow and reverse representations, are considered. Based on these structures, a new algorithm determines the candidate subgraphs and prunes every subgraph that is either unreachable from the given source vertex <s> or does not lead to the given destination<t>, benefiting from the rich information inherent in the matrix and reverse matrix structure representations of the graph. The experiments were conducted using our heuristic and the conventional shortest path finding, namely Dijkstra’s algorithm. Practical results are given showing considerable improvements of the proposed algorithm in performance. This improves the shortest path algorithm significantly.

Improvement of shortest-path algorithms using subgraphs heuristics. Available from: https://www.researchgate.net/publication/281061037_Improvement_of_shortest-path_algorithms_using_subgraphs_heuristics [accessed Jan 17, 2017].