Tech-Algorithm.com

The algorithm will be much easier to understand when we see it in action. Here is an applet demonstrating dijkstra's algorithm process when roaming a network. In this demonstration, our search begin at node 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 :)