An Efficient Heuristic Shortest Path Algorithm Using Candidate Subgraphs

Abstract

Given a graph G=(V,E,w), where Vand E are finite set of vertices and edges respectively, in a directed weighted graph G with weights denoted by w(e)>0 for each edge e∈ E. Given two vertices <s> and <t>∈ V, P(s,t) is the shortest path between <s> and <t> containing the least sum of edge-weights on the path from <s> to <t>. The properties of the graph representation, using matrix structures to represent the graph in normal flow and reverse representations, are considered. Based on these structures, the 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 structure representations of the graph