An algorithm for finding shortest paths in undirected graphs with using the nearest neighbor search technique

摘要

We deal with the problem to find a shortest path between two specified vertices. This problem can be efficiently solved with A {sup}* algorithm, used in Al field, if we roughly know the distance from each vertex to the goal vertex. On the other hand, LAESA, one of nearest neighbor search algorithms, uses "approximate distance" to solve NNS problem efficiently. In this paper, we show that approximate distance can be applied to A {sup}* algorithm, and that can efficiently obtain shortest paths with this method.