Finding all-pairs shortest path for a portion of nodes

user_8028576 0
Viewed 227

Using NetworkX "all_pairs_dijkstra_path" function, it is possible to find all-pairs shortest paths in a graph G. Now, assume, the graph G is so large, say includes 100,000 nodes, and I am only interested in finding the shortest paths for a subset of the nodes, say 1,000 randomly drawn nodes.

Using the "dijkstra_path" function of NetworkX, I can loop over the subset of nodes and find what I am looking for. However, doing so does not seem to be efficient as I would be calling the function n times (assuming the length of the subset is n) and the so far investigated information would be discarded. I read multiple posts mentioning that all_pairs functions are better for searching paths between all pairs rather than using single source-to-target functions in a loop. Is there a way to provide a subset of nodes as an input in NetworkX? Or what is the next best approach?

The question is a duplicate of this unanswered question.

shortest-path networkx python
1 Answers

Specifically for all_pairs_dijkstra_path of networkx, you will not loose any performance to calling n times single_source_dijkstra_path. This will become clear if you look at the implementation of all_pairs_dijkstra_path:

def all_pairs_dijkstra_path(G, cutoff=None, weight="weight"):
    """ < docs """
    path = single_source_dijkstra_path
    # TODO This can be trivially parallelized.
    for n in G:
        yield (n, path(G, n, cutoff=cutoff, weight=weight))

If you need more information, you should be more specific about your situation:

  • directed vs. undirected
  • unweighted vs weighted, if weighted which kind of weights, e.g. negative weights possible?
  • is it a directed acyclic graph? or any other specific kind of graph?
  • is the usage of the cutoff (see function above) applicable in your use case?
  • is the graph a single (strongly) connected component?

But probably more importantly, have you simply tried the loop over the 1000 nodes? (or start with 30 and check the runtime). Many things would depend on your use case and what you want to calculate or approximate.

user_113393110
Related