/**
*
* This demo program simulates dijkstra's algorithm described in the article.
* below is a sample output of this program:
*
* -----------------------------------------------------
* finding shortest path from [g] to [f]
* g has been selected. finding all neighbors...
* g->b [1.0] [b added to open list]
* g->d [2.0] [d added to open list]
* g->h [0.5] [h added to open list]
* g has been moved to closed list.
* h has been selected. finding all neighbors...
* neighbor d is already in open list.
* h->d [1.0] is a shorter path!
* h has been moved to closed list.
* b has been selected. finding all neighbors...
* b->a [2.0] [a added to open list]
* b->c [3.0] [c added to open list]
* b has been moved to closed list.
* d has been selected. finding all neighbors...
* neighbor c is already in open list.
* d->c [2.0] is a shorter path!
* d->e [2.0] [e added to open list]
* d has been moved to closed list.
* a has been selected. finding all neighbors...
* neighbor e is already in open list.
* a->f [3.0] [f added to open list]
* a has been moved to closed list.
* c has been selected. finding all neighbors...
* c has been moved to closed list.
* e has been selected. finding all neighbors...
* neighbor f is already in open list.
* e has been moved to closed list.
* f has been selected. finding all neighbors...
* f has been moved to closed list.
* tracing from [f] to [g]
* f->a->b->g
* -----------------------------------------------------
*
* code was not written to be professional but for readability.
*
* www.tech-algorithm.com
*
*/
import java.util.Iterator;
import java.util.LinkedList;
public class DijkstraAlgorithm {
public DijkstraAlgorithm() {
LinkedList open = new LinkedList() ;
LinkedList closed = new LinkedList() ;
// Node is a custom class made just for this demo
// by default all nodes is neither in open or closed list
Node a,b,c,d,e,f,g,h ;
a = new Node("a") ;
b = new Node("b") ;
c = new Node("c") ;
d = new Node("d") ;
e = new Node("e") ;
f = new Node("f") ;
g = new Node("g") ;
h = new Node("h") ;
// connect nodes according to connections from the article
// the floating numbers are the movement costs
a.connectNode(b,1.0f) ;
a.connectNode(e,2.0f) ;
a.connectNode(f,1.0f) ;
b.connectNode(g,1.0f) ;
b.connectNode(c,2.0f) ;
c.connectNode(d,1.0f) ;
d.connectNode(e,1.0f) ;
d.connectNode(g,2.0f) ;
d.connectNode(h,0.5f) ;
e.connectNode(f,2.0f) ;
g.connectNode(h,0.5f) ;
// we want to finding the shortest path from node g to node f
Node start = g ;
Node end = f ;
// shortest path from start -> end
// put first node in the open list
System.out.println("finding shortest path from ["+start.getName()+"] to ["+end.getName()+"]") ;
start.setOpen(true) ;
open.add(start) ;
while (true) {
Iterator o = open.listIterator() ;
// if there is no more item in the open list, the search is done
if (!o.hasNext()) break ;
// get the lowest overall cost node from open list
Node node = (Node)o.next() ;
while (o.hasNext()) {
Node temp = (Node)o.next() ;
if (temp.getOverallCost()"+endNode.getName()+
" ["+endNode.getOverallCost()+"] ["+ endNode.getName()+" added to open list]") ;
} else {
// check if this path is shorter than previous
System.out.println("\tneighbor "+endNode.getName()+" is already in open list.") ;
if ((node.getOverallCost() + path.getCost()) < endNode.getOverallCost()) {
endNode.setParent(node) ;
endNode.setOverallCost(
node.getOverallCost()+path.getCost()) ;
System.out.println("\t"+node.getName()+"->"+endNode.getName()+
" ["+endNode.getOverallCost()+"] is a shorter path!") ;
}
}
}
// put selected node to closed list
node.setClosed(true) ;
closed.add(node) ;
open.remove(node) ;
System.out.println(node.getName()+" has been moved to closed list.") ;
// once target (end node) put into closed list the search is done
if (node.equals(end)) break ;
}
// now trace back from [end] -> [start] by parent
System.out.println("tracing from ["+end.getName()+"] to ["+start.getName()+"]") ;
Node prev = end.getParent() ;
String line = end.getName() ;
while (prev != null) {
line = line + "->"+prev.getName() ;
end = prev ;
prev = prev.getParent() ;
}
System.out.println(line) ;
}
public class Node {
private String name ;
private Node parent ;
private float overallCost ;
private LinkedList paths ;
private boolean open, closed ;
public Node(String name) {
this.name = name ;
parent = null ;
overallCost = 0.0f ;
paths = new LinkedList() ;
setOpen(false) ;
setClosed(false) ;
}
public void connectNode(Node toNode,float cost) {
// check if already connected to avoid duplicate connection
Iterator i = paths.listIterator() ;
Path path ;
while (i.hasNext()) {
path = (Path)i.next() ;
if ((path.getEndA().equals(toNode)) || (path.getEndB().equals(toNode))) {
System.out.println(getName()+" is already connected to "+toNode.getName()) ;
return ; // already connected to the node
}
}
// connect this node with toNode
path = new Path(this, toNode, cost) ;
paths.add(path) ;
toNode.addPath(path) ;
}
public void addPath(Path path) {
// check if path already exist to avoid duplicate
Iterator i = paths.listIterator() ;
while (i.hasNext()) {
Path p = (Path)i.next() ;
if (p.equals(path)) {
System.out.println("The path already exists!") ;
return ;
}
}
paths.add(path) ;
}
public Iterator getNeighbors() {
return paths.listIterator() ;
}
public void setParent(Node newParent) {
parent = newParent ;
}
public Node getParent() {
return parent ;
}
public void setOverallCost(float newCost) {
overallCost = newCost ;
}
public float getOverallCost() {
return overallCost ;
}
public boolean isOpen() {
return open;
}
public void setOpen(boolean open) {
this.open = open;
}
public boolean isClosed() {
return closed;
}
public void setClosed(boolean closed) {
this.closed = closed;
}
public String getName() {
return name;
}
}
public class Path {
private Node endA, endB ;
private float cost ;
public Path(Node endA, Node endB, float cost) {
this.endA = endA ;
this.endB = endB ;
this.cost = cost ;
}
public float getCost() {
return cost ;
}
public Node getEndA() {
return endA ;
}
public Node getEndB() {
return endB ;
}
public Node getEndNode(Node startNode) {
if (endA.equals(startNode))
return endB ;
if (endB.equals(startNode))
return endA ;
return null ;
}
}
public static void main(String[] args) {
new DijkstraAlgorithm() ;
}
}