
One type consists of all-shortest-paths and all-distances queries, when querying a vertex yields either shortest paths from that vertex to all other vertices [1]}, [2]} or distances from that vertex to all other vertices [3]}. The latter, of course, is less informative.

A more refined type of query oracles, suggested in [1]}, [3]}, consists of shortest-path and distance queries, when querying a pair of vertices yields either a shortest path or the distance between them [6]}, [7]}, [8]}. Again, the latter is less informative.

