CODEWITHSUNDEEP
pythonnetworkxgraph-theory
PPR
PPR

Reputation: 417

Efficent algorithm for finding the shortest paths from ALL nodes to a node?

I am interested in finding the shortest path from all points to a specific point in a network. Till now, I have been estimating this by calculating the shortest path by looping through all points.

This approach is computationally expensive as the size of the network increases. Is there an efficient alternative? Anything in NetworkX that I overlooked?

# Pseudocode 
For a_node in list_of_nodes:
  shortest_path_to_poi = nx.shortest_path(G, source=a_node, target=poi, method='dijkstra')

Thanks for your time and condideration.

Upvotes: 1

Views: 408

Answers (1)

David E
David E

Reputation: 1444

Dijkstra's algorithm typically is implemented by finding all the shortest paths from a source node to every other node - see eg wikipedia. In NetworkX, you can use nx.single_source_dijkstra.

lengths, paths = nx.single_source_dijkstra(G, source=poi)
# paths[v] is the shortest path from poi to the vertex with index v

See also the shortest paths reference in the nx docs.

Upvotes: 4

Related Questions