1
$\begingroup$

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 s where the cost of the shortest path from the starting node s to e is not greater than C.
  • For each e in 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.

$\endgroup$
  • $\begingroup$ Are you looking for an algorithm? I think you already figured out that using Dijkstra's algorithm, with an early termination when cost constraint is violated, is a good start. Probably not for parallel computing though. $\endgroup$ – peterwhy Jul 9 '15 at 23:56
  • $\begingroup$ @peterwhy Ultimately, yes, I'm looking for an algorithm. Dijkstra is trivial and will work well for small number of queries. What I need is to calculate many queries (starting from different sources) in parallel. I'll update the question with a description of the practical problem. $\endgroup$ – lexicore Jul 10 '15 at 5:20
0
$\begingroup$

Correct terminology for your problem would be "Single source Shortest path problem"

Maybe you should try implementing the data structure (priority queuefor dijkstra) as fibonacci heap which has less running time

Hope this helps

$\endgroup$
  • $\begingroup$ I hope my question already hints that I'm somewhat aware of the "shortest path" theory. What I have in focus is not just shortest path but a "reachable area". I'm quite sure this must be calculatable better in better time than just Dijkstra mit Fibonacci priority queue. $\endgroup$ – lexicore Jul 15 '15 at 9:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.