4
$\begingroup$

I didn't succeed to find an algorithm that finds the shortest path in a weighted non directed graph between all pairs of nodes whose shortest path distance are inferior to a specific number. I think that, especially if the maximum distance is very small, it should significantly improve my algorithm's performance. Do you know such an algorithm ?

For example : let's say I set a maximum distance of 30. If the shortest path between A and B is 10, I want the algorithm to find it (and provide me the distance). If the shortest path between B and C is 50, I don't want the algorithm to find it.

Thanks,

Improve this question
$\endgroup$
6
  • $\begingroup$ Do you have a directed graph? Are there weights (distance values) on your edges? A* is a good algorithm to use.. just have it exit early or return nothing if the path discovered it too long. $\endgroup$
    – Rob
    Commented Feb 23, 2016 at 19:42
  • $\begingroup$ The graph is not directed. There are weights on my edges. I want to get the distance between all nodes (with a distance between them inferior to a specific number), will A* work efficiently here too ? $\endgroup$
    – sdrdis
    Commented Feb 23, 2016 at 20:20
  • $\begingroup$ Yes as long as you do not have negative weights on the edges.. If you do just add the value of of the most negative weight to every edge so that all the weights are all positive. $\endgroup$
    – Rob
    Commented Feb 23, 2016 at 20:23
  • 1
    $\begingroup$ OH sorry I did not read the all pairs of nodes.. in that case you want to use Dijkstra's algorithm. You just need to run it with each node as the source node. :) every run will give you the shortest path from the source to every other reachable nodes in the graph. $\endgroup$
    – Rob
    Commented Feb 23, 2016 at 20:28
  • $\begingroup$ I'm skeptical that you can find such an algorithm, for the following reason. Suppose the shortest path between A and C is 50, so you don't care if the algorithm finds it. But this path might first go from A to B and then from B to C, and these are both shortest paths of lengths less than 30 (let's say), so you do want the algorithm to find those. So you're only saving yourself the easy work ... even if almost all pairs of nodes have farther distance than your max, it feels like you only could save yourself $O(n^2)$ work off an $O(n^3)$ algorithm. (unless the graph is sparse) $\endgroup$
    – usul
    Commented Feb 24, 2016 at 8:46

2 Answers 2

Reset to default
1
$\begingroup$

maybe this paper, in which the calculation of the all pairs shortest paths in $O(n^2)$ with high probability is solved, meets your requirements.
Some preconditions about the distribution of edge lengths are made, which you could check against the properties of your problem instances.

Improve this answer
$\endgroup$
1
$\begingroup$

Interpreting your question that you want to find the shortest paths in order of increasing length, then a nested Dijkstra algorithm may solve your problem also in case of directed graphs.
I assume you are familiar with the Dijkstra algorithm, so I shorten the explanation to the essential:

  • create the $n\times n$ distance table and set its diagonal elements to $0$ and the off-diagonal elements to $+\infty$

  • create for every vertex $v_i$ a priority queue $q_i$ just as in the ordinary Dijksta algorithm and push $v_i$ into $q_i$

  • create a second "meta" priority queue $Q$ and push all $q_i$ into it; $Q$ is ordered according to the length of the shortest path from $v_i$ to $q_i$'s top element.

  • while $Q$ isn't empty, perform a "Dijkstra step" (i.e. popping of the top element and possibly relaxing the shortest path length from its root to the popped element) for $Q$'s top element, if that is w.l.o.g $q_i$, then $q_i$'s top element (w.l.o.g. $v_j$) is popped and possibly the length of the shortest path from $v_i$ to that element is relaxed (i.e. distance $d_{ij}$ is updated).
    If $q_i$ isn't empty and if the distance of the new top element is less or equal the threshold value (30 in your example), reinsert it into $Q$

That algorithm will report the routes in ascending order of length and only those whose length doesn't exceed the threshold value.

If you are only interested in the routes and do not care about the order in which they are reported, you can do without $Q$ and start a Dijkstra route calculation for each node separately; each of those calculations can then be stopped if the top element's distance exceeds the threshold.
Using Fibonacci heaps as priority queues the runtime is $O(n(n\log(n)+m))$ where $n$ is the number of vertices and $m$ the number of edges.

Improve this answer
$\endgroup$
5
  • $\begingroup$ That's an interesting solution but what can we say anything about the performance? I'm worried about duplicating a lot of work. $\endgroup$
    – usul
    Commented Feb 24, 2016 at 8:38
  • $\begingroup$ @usul Without further information not much can be said; if you know an upper bound for the shortest path you are interested in and if you know,that the triangle inequality may be violated, then you can filter out all edges that are longer, before actually calculating the paths. It is probably as with sorting: if you have information about the number of inversion you can use a specialized algorithm that will perform poor in the worst case. The same applies to this problem. $\endgroup$
    – Manfred Weis
    Commented Feb 24, 2016 at 10:29
  • $\begingroup$ @usul the overhead doesn't come from duplicated work, but rather by evenly growing the shortest path trees according to distance; so the algorithm simulates throwing n stones simultaneously into the water instead to one by one as is ordinarily done when calculating the APSP for sparse graphs by repeated application of the Dijkstra algorithm for each node. $\endgroup$
    – Manfred Weis
    Commented Feb 25, 2016 at 7:43
  • $\begingroup$ Why have you deleted your meta post meta.mathoverflow.net/questions/2768/… , after just half an hour? $\endgroup$
    – Stefan Kohl ♦
    Commented Feb 28, 2016 at 17:58
  • $\begingroup$ @StefanKohl it was because of the comments stating it would be inappropriate; but feel free to undelete it. $\endgroup$
    – Manfred Weis
    Commented Feb 28, 2016 at 18:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .