6
$\begingroup$

I know that there are All Pairs Shortest Paths algorithms. But I am not sure if they are effective if I am trying to solve the Pairs-Shortest-Path problem for a subset of my vertexes.

The properties of the graph are:

  • sparse
  • directed
  • positive arc weights
  • cycle-free
  • the subset of vertexes I am interested in is 1/14 of |V|

Currently I am solving this problem with johnsons APSP algorithm but I am interested if there are more efficient ways.

Keywords for further research or suggestions are welcome.

$\endgroup$
  • $\begingroup$ You can implement the "some" on one side by using single-source algorithms only for some start nodes. How much does that help? (Recall that "n times Dijkstra" is actually just as efficient as the best known APSSP algorithms, at least in the general and worst case). $\endgroup$ – Raphael Dec 1 '14 at 18:15
  • $\begingroup$ yes, what I was thinking about, was reusing the information generated by the other calls. But it should be actually not too hard to proof, that for all possible algorithms the complexity is going to be at least the same. So we are trying to push some factors. It may be, that calling the single source dijkstra for the interesting nodes seperatly needs longer than johnsons. I will benchmark this tomorrow... $\endgroup$ – thi gg Dec 1 '14 at 22:16
  • $\begingroup$ Can you do preprocessing on the graph? I.e. is this a single query problem, or a repeated queries problem? $\endgroup$ – jkff Dec 2 '14 at 5:00
  • $\begingroup$ the underlying graph may change but the subset of nodes is always the same. $\endgroup$ – thi gg Dec 2 '14 at 10:05
  • $\begingroup$ will this work? you create new nodes $s$, $t$ connected to the two separate sets as suggested by Viola $\endgroup$ – vzn Dec 2 '14 at 16:07

Your Answer

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

Browse other questions tagged or ask your own question.