search

nanodeath / CrowLib

Crow: Find your shortest path!
http://www.effectgames.com/effect/article.psp.html/community/Pathfinding_library_Dijkstra_s_Algorithm
MIT License
40 stars 6 forks source link

Dijkstra's wastes memory and time queuing nodes already in the queue #11

Open damium opened 12 years ago

damium commented 12 years ago

It also causes problems when using a function to filter and gather info as nodes are in the visited list more than once. If a node is already in the queue it should look to see which path is shorter and select it.

I'm not positive that this is the best place for the fix, possibly it would be cleaner to apply it to the queue itself.

nanodeath commented 12 years ago

@damium Sorry I suck, I first looked at this quite a while ago but forgot to respond.

Can you explain why you added the Graph#replaceNode method? You're not actually using it.

Regarding the extra-nodes-trimming, I think that part looks good. I think the complexity adding that sort of functionality to the queue would be inappropriate, given it's supposed to be just a plain priority queue.

damium commented 12 years ago

I'm using the replaceNode method in another project so it was mainly for my use there and was added after I opened the pull request for the original fix. I'm not sure if it would be generally useful.