# About the memory consumption of dijkstra on dense graph

This topic is 707 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 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 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 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 on other sites
Interesting, however the OP doesn't state which form of the algorithm he's using :)

Based on memory consumption I'd say the O(n^2) variant is most likely...

##### Share on other sites
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.

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

1. 1
2. 2
3. 3
Rutin
15
4. 4
5. 5

• 10
• 9
• 9
• 11
• 11
• ### Forum Statistics

• Total Topics
633682
• Total Posts
3013308
×