org.samcrow
Class DijkstraAlgorithm

java.lang.Object
  extended by org.samcrow.DijkstraAlgorithm

public class DijkstraAlgorithm
extends java.lang.Object

Finds routes
Based mostly on http://www.vogella.de/articles/JavaAlgorithmsDijkstra/article.html

Author:
Sam Crow

Field Summary
private  java.util.Map<Node,java.lang.Double> distance
           
private  java.util.List<Link> Links
           
private  java.util.List<Node> nodes
           
private  java.util.Map<Node,Node> predecessors
           
private  java.util.Set<Node> settledNodes
           
private  java.util.Set<Node> unSettledNodes
           
 
Constructor Summary
DijkstraAlgorithm(Graph graph)
           
 
Method Summary
 void execute(Node source)
           
private  void findMinimalDistances(Node node)
           
private  double getDistance(Node node, Node target)
           
private  Node getMinimum(java.util.Set<Node> Nodees)
           
private  java.util.List<Node> getNeighbors(Node node)
           
 java.util.LinkedList<Node> getPath(Node target)
          This method returns the path from the source to the selected target and NULL if no path exists
private  java.lang.Double getShortestDistance(Node destination)
           
private  boolean isSettled(Node Node)
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

nodes

private java.util.List<Node> nodes

Links

private java.util.List<Link> Links

settledNodes

private java.util.Set<Node> settledNodes

unSettledNodes

private java.util.Set<Node> unSettledNodes

predecessors

private java.util.Map<Node,Node> predecessors

distance

private java.util.Map<Node,java.lang.Double> distance
Constructor Detail

DijkstraAlgorithm

public DijkstraAlgorithm(Graph graph)
Method Detail

execute

public void execute(Node source)

findMinimalDistances

private void findMinimalDistances(Node node)

getDistance

private double getDistance(Node node,
                           Node target)

getNeighbors

private java.util.List<Node> getNeighbors(Node node)

getMinimum

private Node getMinimum(java.util.Set<Node> Nodees)

isSettled

private boolean isSettled(Node Node)

getShortestDistance

private java.lang.Double getShortestDistance(Node destination)

getPath

public java.util.LinkedList<Node> getPath(Node target)
This method returns the path from the source to the selected target and NULL if no path exists