Fast algorithm for peer-to-peer shortest path problem

摘要

A plurality of landmarks selected from a source weighed graph on which a path search is performed; and the shortest path lengths between landmarks, and the shortest path lengths from vertices to landmarks adjacent to the respective vertices are calculated, and are stored in a memory device so as to be later referable. Routines for calculating upper and lower limits of the shortest path length corresponding to two vertices v and w are prepared by using expressions derived from quadrangle inequalities formed of the two vertices v and w as well as two landmarks adjacent to the respective vertices v and w. In response to a call from an A* search program, these routines return the upper limit or the lower limit of the shortest path length corresponding to v and w by referring to the shortest path lengths between landmarks, and the shortest path lengths from vertices to landmarks adjacent to the respective vertices, which have been previously stored in the memory device.