Dijkstra's algorithm java applet interactive demo

18 October 2007, 12:18 PM

*g*and ends only after all node has been visited. Try clicking and keep clicking the applet to conduct step-by-step search. You will notice nodes and paths changing colors.

- 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

~

**hello world**, 24 August 2012, 06:05 AMNetBeans asking for main method

Post a comment~

~~~, 24 November 2010, 08:07 PM