I'm considering the following problem (very rough description):
Assume we have a graph where edges are assigned some non-negative costs, a starting node
s and some cost constant
C. Find out:
- A set of nodes
e, reachable from
swhere the cost of the shortest path from the starting node
eis not greater than
- For each
ein the set the above - the cost of the shortest path.
Basically Dijkstra with the cost constraint.
My primary question is: what is the correct terminology in the graph theory for this problem?
I've been looking at "accessibility" or "reachability" but these seem to be wrong keywords.
Ultimately I'm looking for an algorithm which could efficiently answer many such queries on one (non-modifable) but quite large (potentially ~100mln edges) graph in parallel. I'd like to check literature but need hints on the right keywords.
Update: My practical problem is as follows.
Assume we're given a continental-size road network (modelled as a directed graph, with some properties on edges and nodes like if it's a pedestrian way or highway). Edge cost ist travel time.
I'd like to answer user queries like: starting from some given position (graph node), which nodes are reachable withing 1 hour?
I'd also like to answer these queries very fast (<200-300ms, if possible) for many users (>10000, if possible) in parallel.
I think there should be at least two optimizations possible:
- Some reasonably-sized precomputation, for instance pre-computed distance matrices for selected "central" nodes.
- If searches are conducted in parallel, they may profit from "temporary results" of each other.
I have a few ideas on my own but I'd first like to check the literature to avoid reinventing the wheel.