dijkstraalgorithm.java.svn-base

這是一個JAVA語言寫的多代理人程式用來模擬飛機起飛或是降落的程式

package dijkstra;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.List;
import java.util.Map;


public class DijkstraAlgorithm<E, W> {
	Collection<Node<E, W>> nodes;
	Map<Node<E, W>, Boolean> checked;
	Map<Node<E, W>, Double> distance;
	Map<Node<E, W>, Node<E, W>> previous;
	Node<E, W> root;
	Node<E, W> target;
	List<E> edge_path;
	
	public DijkstraAlgorithm(Node<E, W> root, Node<E, W> target, Collection<Node<E, W>> nodes) {
		this.root = root;
		this.target = target;
		this.nodes = nodes;
	
		reset();
	}
	
	public DijkstraAlgorithm(Collection<Node<E, W>> nodes) {
		this.nodes = nodes;
		
		reset();
	}
	
	public void reset() {
		checked = new HashMap<Node<E, W>, Boolean>();
		distance = new HashMap<Node<E, W>, Double>();
		previous = new HashMap<Node<E, W>, Node<E, W>>();
		
		for (Node<E, W> node : nodes) {
			checked.put(node, false);
			distance.put(node, Double.POSITIVE_INFINITY);
			previous.put(node, null);
		}
		distance.put(root, 0.0);
	}
	
	public void set_root(Node<E, W> root) {
		this.root = root;
		
		distance.put(root, 0.0);
	}
	
	public void set_target(Node<E, W> target) {
		this.target = target;
	}
	
	public void calculate_distance() {
		
		Node<E, W> to_check;
		
		while ((to_check = get_closest_nonchecked()) != null) {
			calc_node(to_check);
		}
			
	}
	
	public void calculate_edge_path() {
		edge_path = new ArrayList<E>();
		
		Node<E, W> to_check = target;
		Node<E, W> previous_node = null;
		while (to_check != root) {
			previous_node = previous.get(to_check);
			edge_path.add(0, previous_node.neighbors.get(to_check).object);
			to_check = previous_node;
		}
	}
	
	public List<E> get_edge_path() {
		if (edge_path == null)
			calculate_edge_path();
		
		return edge_path;
	}
	
	public Double get_distance() {
		return distance.get(target);
	}
	
	public void calc_node(Node<E, W> new_root) {
		
		Double temp_dist;
		for (Node<E, W> node : new_root.neighbors.keySet()) {
			temp_dist = distance.get(new_root);
			temp_dist += new_root.neighbors.get(node).distance;
			if (temp_dist < distance.get(node)) {
				distance.put(node, temp_dist);
				previous.put(node, new_root);
			}
		}
		checked.put(new_root, true);
	}
	
	public Node<E, W> get_closest_nonchecked() {
		Node<E, W> closest = null;
		for (Node<E, W> node : nodes)
			if (!checked.get(node))
				if (closest == null)
					closest = node;
				else if (distance.get(node) < distance.get(closest))
					closest = node;
		return closest;
	}
}