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.