CODEWITHSUNDEEP
pythonnetworkxshortest-pathdijkstra
Leo
Leo

Reputation: 232

Is there a more efficient way to calculate the shortest path problem than networkx in python?

I am calculating the shortest path from one source to one goal on a weighted graph with networkx and single_source_dijkstra.

However, I run into memory problems.

Is there a more efficient way to calculate this? An alternative to Networkx? See my code:

   cost, shortestpath = nx.single_source_dijkstra(graph, startpointcoords, secondptcoords,cutoff=10000000)

Upvotes: 3

Views: 808

Answers (3)

Joel
Joel

Reputation: 23907

The bidirectional dijkstra algorithm should produce a significant improvement. Here is the documentation.

A good analogy would be in 3D: place one balloon at point x and expand it till it reaches point y. The amount of air you put in is proportional to the cube of the distance between them. Now put a balloon at each point and inflate both until they touch. The combined volume of air is only 1/4 of the original. In higher dimensions (which is a closer analogy to most networks), there is even more reduction.

Upvotes: 2

BrunoSE
BrunoSE

Reputation: 94

Perhaps try using another algorithm? Your graph may have too many vertices but few edges, in which case you could use Bellman-Ford bellman_ford_path() link in networkX

Another solution would be to use another python package, for example the answers to this question has different possible libraries.

The last solution would be to implement your own algorithm! Perhaps Gabow's algorithm, but you would have to be very efficient for example by using numpy with numba

Upvotes: 0

Leo
Leo

Reputation: 232

Apparently the A* Algorithm of networkx is way more efficient. Afterwards I calculate the length of the resulting path with the dijkstra algorithm I posted.

Upvotes: 1

Related Questions