Dijkstra's algorithm java applet interactive demo
18 October 2007, 12:18 PM
- white node is unseen
- magenta node is open
- gray node is closed
The term open and closed is actually the term fringe and tree respectively as described in most graph theory books. An open node is a node that is visible to the network crawler but not yet visited. Open nodes are candidates for the next destination of the search. Gray nodes are one that has been visited and will never be visited again. Movement cost is the cost of moving from one node to another immediate node. It can be a distance, risk, traffic jam factor, etc.
- numbers between lines are the movement costs.
- red arrow line indicates child->parent relationship but not yet confirmed.
- black arrow line indicates child->parent relationship that has been confirmed.
Klik the applet!
Once a search is complete, all node is gray, one can find the shortest path from any node back to the starting node g by following the arrows leading back to node g.
To over-simplify the algorithm, rule of selecting the next magenta node is to choose the one that has the smallest cumulative movement cost from the starting point.
Read Dijkstra's algorithm full article for detailed explanation.
Java applet codes
The applet is consisted of four java files,
- DijkstraDemo.java is the applet.
- Node.java
- Path.java
- BoxFilter.java for the soft smoothing effect :)
Last edited on 29 March 2009
Comments
~~~~, 24 November 2010, 08:07 PM
tnx
~hello world, 24 August 2012, 06:05 AM
NetBeans asking for main method
Post a comment~