With the dijkstra algorithm,

I have to do 3 nested loops to find all shortest-paths.

What about the Floyd-Warshall Algorithm,

How does it work?

If I understand the terms correctly, if A goes to C which passes thru B

the cost of A to C is c(A,B) + c(B,C)

but when I search for some examples on the net,

they are still using 3 nested loops, so how can I work faster than the dijkstra's...

I can't take the complexity of the dijkstra's because

if I have for example 9000 nodes, it is impossible to do that

it has to finish under 2 minutes.

But I have up to 2000 nodes, it can finish within 10 minutes,

For 9000 nodes, it is going crazy....

I am not sure if this works better if I optimize the program and

how does it perform in release build.

But that's what I've got so far.

Thanks

Jack

IIRC, i've used Dijkstra on bunny model (about 4000 vertices), and it took maybe 20 seconds.

I may be wrong with exact numbers, but i strongly suggest you try the release build.

You can expect a speedup of at least 10x or much more, depending what debug checks there are (stl range check etc.)

To get a faster algorithm, you could build clusters to reduce node count and use it for a low res graph handling large distances.

But this might be some work...

I've done something like this before. If you don't mind pre-computing node distances and storing the info, then this will work.

Each node should know its neighbor and how far it is to it -- this is where you would start. Make a while-loop so that each node looks to its neighbors for info about their neighbors until each node has a "path distance" from itself to each node within the system. The data would look something like this:

struct NODETOINFO{

int node;

int distance;

bool neighbor;

};

Like I said, each node will have this info for each node within the system. You could reduce the size by using "short" or "byte"......

The problem is that you need to know the initial neighbor information (at least which ones are the neighbors). This isn't usually a problem because you would place the nodes in a pattern anyway.

Hope this helps.

I can't take the complexity of the dijkstra's because if I have for example 9000 nodes, it is impossible to do that it has to finish under 2 minutes.

But I have up to 2000 nodes, it can finish within 10 minutes, For 9000 nodes, it is going crazy....

Your implementation needs tuning. It shouldn't take that long.

As mentioned above, start with a release build rather than a debug build. Use a profiler to ensure you are doing everything right.

There are many things that could be slowing your system down. Two of the common problems are memory allocations since that is a slow process, and data locality destroying cache effects. The algorithm should not be doing any memory allocation, working instead with existing large buffers. Make sure the objects are arranged in contiguous memory with direct access, not a data structure with indirect memory access.

Your profiler will likely find other issues and hot spots. Find and eliminate those from the central loops.

Thanks man! In the 2000 nodes scenario, when doing that in Release Optimized mode,

it completes the job in 9 seconds... The maximum duration I can accept is up to about 5 minutes.

Although sometimes the computer can finish the task within a nice good time, now the problem falls back

to the number of nodes to open during the search at real time.

Actually, I am thinking about merging some parts of the octree,

so that the dijkstra really doesn't matter that much.

I think I should open another thread about how to merge certain parts of the octree.

Because the octree is already in place, or not call it an octree,

because they are just voxels in the scene everywhere......

But I think the stitching or merging need some work to do in order to go okay.

Because if I start off with a set of octree built, I have to set a certain threshold and prune a seed

to the octree, and start merging from there, otherwise, I need to rebuild the octree module from scratch again.

Thanks

Jack