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

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.

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.

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...

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.