I found on a 2500K CPU @ 3.2GHz, 16GB RAM.

With 700 nodes, it takes 6 seconds

With 7000 nodes, it can not withstand.... I just stopped it because it just took too long before it finished.

Does anyone know, in general, the amount of nodes a dijkstra can handle?

The algorithm is O(N^3)/3 for the time being

I can't express it, but it is like

with 700 nodes

for (int i = 0; i < _nodes.size(); i++)
   for (int j = i+1...
      for (int k = j+1

because I advance the count variable in each inner loop.

BTW, it is not optimized (debug build)

Thanks

Jack

Dijkstra's minimum path between a pair of points routine is the famous algorithm you are probably writing about, he had several major algorithms so you might mean another.

The single pair algorithm potentially takes quite a lot of memory when implemented naively, on the order of N^3 sounds correct. Most games use the A* (A star) algorithm, which is Dijkstra's single pair shortest path algorithm plus a small heuristic value to speed up the search a bit, at the cost of potentially not being optimal.

Since you mention "flood fill", I'm guessing you are talking about an all-pairs shortest path algorithm? Those exist, but are much more memory intensive for anything other than just storing a binary reachable status. Using the single pair shortest path over and over for all pairs is a bit extreme.

You might also mean having a path that follows a space filling curve across an entire board. That can take as much resources as your path requires, entirely dependent on your implementation.

Finally, there are many implementations of these algorithms online, some quite efficient and others are terribly inefficient. Can you share what implementation you are following?

Slightly off topic, but I want to ask.

Most games use the A* (A star) algorithm, which is Dijkstra's single pair shortest path algorithm plus a small heuristic value to speed up the search a bit, at the cost of potentially not being optimal.

In which cases it would not be optimal? I thought it always takes the most optimal path.

Slightly off topic, but I want to ask.

Most games use the A* (A star) algorithm, which is Dijkstra's single pair shortest path algorithm plus a small heuristic value to speed up the search a bit, at the cost of potentially not being optimal.

In which cases it would not be optimal? I thought it always takes the most optimal path.

Given your heuristic never overestimates, it IS optimal afaik.

Dijkstra's minimum path between a pair of points routine is the famous algorithm you are probably writing about, he had several major algorithms so you might mean another.

The single pair algorithm potentially takes quite a lot of memory when implemented naively, on the order of N^3 sounds correct. Most games use the A* (A star) algorithm, which is Dijkstra's single pair shortest path algorithm plus a small heuristic value to speed up the search a bit, at the cost of potentially not being optimal.

Since you mention "flood fill", I'm guessing you are talking about an all-pairs shortest path algorithm? Those exist, but are much more memory intensive for anything other than just storing a binary reachable status. Using the single pair shortest path over and over for all pairs is a bit extreme.

You might also mean having a path that follows a space filling curve across an entire board. That can take as much resources as your path requires, entirely dependent on your implementation.

Finally, there are many implementations of these algorithms online, some quite efficient and others are terribly inefficient. Can you share what implementation you are following?

As has been said, so long as your heuristic does not overestimate (the heuristic is always less than or equal to the actual optimal path cost) it is guaranteed to be optimal. Also, to note, A* can run faster if you do not require an optimal path, so that's also something to keep in mind... though if you really want greedy best-first search, don't use A* as that has the bookkeeping logic required to keep track of the length of the path so far which is what let's A* not be greedy.

Without knowing what exactly he's doing, though, it is impossible to recommend an ideal solution. Floodfill can be used for anything from pathfinding, to image editing, to determining if two voxel volumes connect, to other things. They're all just functionally graph-processing algorithms. There's other ways to do pathfinding as well (that generally couple with A*), including preprocessing certain pairs (jump point search - it basically identifies obstructions and preprocesses the pairs at the corners so you can get around blocking corners with 1 test), using hierarchical space above the nodes to quickly check path validity, and so on. That, and different algorithms are used if your map is dynamic vs static.