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.

Improve this question
$\endgroup$
6
  • $\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, 2014 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, 2014 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, 2014 at 5:00
  • $\begingroup$ the underlying graph may change but the subset of nodes is always the same. $\endgroup$
    – thi gg
    Dec 2, 2014 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, 2014 at 16:07

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.