Ellipse-based shortest path algorithm for typical urban road networks
Shiming Wang · Systems Engineering - Theory & Practice · 2011
An efficient and reliable optimal path algorithm within restricted searching area is proposed in this paper.Based on the common characteristics of typical urban road networks rather than the statistical information of a certain special city it can be used in different urban road networks.This algorithm searches for the shortest path in two kinds of different size ellipses for different Euclidean distances between the source station and the destination station.Compared to the ellipse restricted searching area algorithm,theoretical calculation and experimental results both show that this algorithm can reduce the time-complexity by 33%-47%without producing an effect on the reliability of the query results when the source station is far from the destination station.