Sign in to follow this  

About the memory consumption of dijkstra on dense graph

Recommended Posts

I've implemented a dijkstra solver with fibonacci heap.

The speed is okay, but when flooding a 30000+ nodes,

the memory consumption starts to go crazy.

With a 65535 flood, it takes up all my system ram which is 16G,

is it normal?

Thanks

Jack

Share this post


Link to post
Share on other sites
Just out of curiosity, is there a reason you're using dijkstra's algorithm?

I'm guessing for curiosity and educational reasons?

A* is superior for quite a lot of cases including those in pathfinding in games because it's simply a ton more efficient as it uses a heuristic to exclude unlikely nodes from its search.

See: http://stackoverflow.com/questions/1332466/how-does-dijkstras-algorithm-and-a-star-compare

Share this post


Link to post
Share on other sites

Dijkstra's shortest-path algorithm has a space complexity of O(n^2) in the number of nodes n.

 

 

What?  No, Dijkstra's algorithm can and should be implemented with O(n) space complexity.  Aside from the queue itself, you only need two pieces of data per node:

  • The id of the previous node.
  • The cumulative length of the path to the node.

Share this post


Link to post
Share on other sites
Ah, Dijkstra for single-source shortest path is O(n)-space, yes. I was thinking of the all-shortest-paths algorithm which uses an n*n matrix to hold the path distances.

Trouble with being a prolific scientist like Dijkstra is having a lot of things carrying your name ;-)

Share this post


Link to post
Share on other sites

Just out of curiosity, is there a reason you're using dijkstra's algorithm?

I'm guessing for curiosity and educational reasons?

A* is superior for quite a lot of cases including those in pathfinding in games because it's simply a ton more efficient as it uses a heuristic to exclude unlikely nodes from its search.

See: http://stackoverflow.com/questions/1332466/how-does-dijkstras-algorithm-and-a-star-compare

 

I wouldn't say it's superior :3. It's basically Dijkstra with a math function. I personally also make use of Dijkstra's algorithm more than A*. Its flood fill nature is awesome for getting AI to explore the surrounding, or consider various routes.

 

Actually, since OP describes the graph as a "dense graph", it's possible he's using an adjacency matrix for the graph itself. In which case the graph itself already uses O(n^2) memory before Dijkstra's algorithm even starts.

However, dense graph can also mean a large amount of nodes that are tightly packed together, like a grid. In which case he could also be using an adjacency list, or an actual graph.
 

 

I've implemented a dijkstra solver with fibonacci heap.

The speed is okay, but when flooding a 30000+ nodes,

the memory consumption starts to go crazy.

With a 65535 flood, it takes up all my system ram which is 16G,

is it normal?

Thanks

Jack

We can't tell you it's normal that you're using that much ram without knowing the size of each node.

However, I'm willing to bet that it's not normal, and there's an error in the code. Perhaps your code is repeating nodes? In which case it means that you're not properly checking over previously visited nodes.

Edited by Tangletail

Share this post


Link to post
Share on other sites
I wouldn't say it's superior :3. It's basically Dijkstra with a math function

 

The addition of a heuristic makes it superior in any equivalent situation where the heuristic carries at least some useful information. 2D and 3D pathfinding algorithms fit into that category. Your problem, and the original poster's problem, may not...

Edited by Kylotan

Share this post


Link to post
Share on other sites

 

I wouldn't say it's superior :3. It's basically Dijkstra with a math function

 

The addition of a heuristic makes it superior in any equivalent situation where the heuristic carries at least some useful information. 2D and 3D pathfinding algorithms fit into that category. Your problem, and the original poster's problem, may not...

 

 

True enough.

Anyways... I'm gonna go ahead and recommend an optimization for the OP. If you are using a grid or your graph is close enough to a grid, look into Jump Point Search.

Jump Point Search is a different approach on Dijkstra and A*. it takes advantage of the fact that path finding in open areas tends to be fairly symmetrical, and that empty space is just empty space.
Alone it is dijkstra, with a heuristic it is A*. But it does a really good job at exploring dense areas very quickly, with a massively reduced memory complexity.

Even though it is intended to work for uniformed grids, it can actually work pretty well with non uniform grids with a few modifications to the algorithm.

 

There are also several reasons to not use it though.

1. It can be painful to implement in big daddy languages.
2. It's hard to debug.
3. Its very niche.

Edited by Tangletail

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this