On determining the shortest path through a number of intermediate points
Sofie Demeyer, Pieter Audenaert, Mario Pickavet · Ghent University Academic Bibliography (Ghent University) · 2012
In this article, an algorithm is presented which determines in a transportation (road) network the shortest path from an origin to a destination that passes by a number of predefined intermediate points, all given by their geographic coordinates.In general, these points do not coincide with nodes of the graph and we may assume that a point is visited as soon as one of the nodes closest to it is visited.The algorithm searches for the shortest path iteratively from one intermediate point to another.It can be proven that, in particular cases, this algorithm realizes a speedup in comparison with a point-to-point algorithm.