Processing 1.0 - Processing Discourse

We closed this forum 18 June 2010. It has served us well since 2005 as the ALPHA forum did before it from 2002 to 2005. New discussions are ongoing at the new URL http://forum.processing.org. You'll need to sign up and get a new user account. We're sorry about that inconvenience, but we think it's better in the long run. The content on this forum will remain online.

Index › Programming Questions & Help › Programs › Dijkstra's Algorithm

‹ Previous Topic | Next Topic ›

Pages: 1

Dijkstra's Algorithm (Read 1004 times)

st33d

Dijkstra's Algorithm
Dec 4^th, 2006, 4:23pm

I'm working on an overhaul of the Pathfinder library. It's going to be quite different and leave room for other search algorithms to be added.

I'm trying to implement Dijkstra's algorithm but I don't understand my references:

http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml
http://www.actionscript.org/forums/showthread.php3?t=77709
http://www.cs.usask.ca/resources/tutorials/csconcepts/1999_8/tutorial/advanced/dijkstra/dijkstra.html

I've got a demo here, but it's not working correctly (I've pretty much just dragged the astar code into it). I'm planning the dijkstra() method for the library as a method which will build all roads leading to one node or stop after finding a given node (I think it's more interesting than astar in some respects because it builds an entire map of roads).

If anyone has any insights as to what I'm doing wrong or any better references it would help me a lot.

st33d

Re: Dijkstra's Algorithm
Reply #1 - Dec 4^th, 2006, 6:56pm

Wait a minute. I've looked at Tom's code again and figured out the discrepancy.

The main issue was that I needed a connector class to store a memory of the distance between Nodes. This is special to dijkstra because the Nodes aren't necessarily in Euclidean space. Their distance could describe the lag between two computers on a network (which I guess is why it's used as the basis for OSPF).

I've revised the demo.

If anyone has any optimisations to suggest (or if you notice mine's broken), or you've done your own version of dijkstra, please append this thread. Thanks.

Aaron.

Pages: 1

‹ Previous Topic | Next Topic ›