package th;

import java.util.TreeMap;
import java.util.HashMap;
import java.util.Vector;
public class Dijkstra {
	private static HashMap do_dijkstra(Node start, Node end) {
		HashMap d = new HashMap(), p = new HashMap(), qprime = new HashMap();
		TreeMap q = new TreeMap();
		Double inc = .000001, count = 0.0, top;
		Node topnode;
		Node[] links = {null, null, null, null};
		int length, lengthprime;
		q.put((Double)(0 + (count += inc)), start);
		qprime.put(start, (Integer)0);
		while (!q.isEmpty()) {
			top = (Double)q.firstKey();
			topnode = (Node)q.get((Object)top);
			d.put((Object)topnode, top.intValue());
			if (topnode == end) break;
			links[0] = topnode.north; links[1] = topnode.south;
			links[2] = topnode.east; links[3] = topnode.west;
			for (int i = 0; i < 4; ++i) {
				if (links[i] == null) continue;
				length = top.intValue() + 1;
				if (qprime.containsKey((Object)links[i]))
					lengthprime = (Integer)qprime.get((Object)links[i]);
				else
					lengthprime = 0;
				if ((!q.containsValue(links[i]) || length < lengthprime) && !p.containsKey(links[i])) {
					qprime.put((Object)links[i], (Integer)length);
					q.put((Double)(length + (count += inc)), links[i]);
					p.put((Object)links[i], topnode);
				}
			}
			q.remove((Object)top);
			qprime.remove((Object)topnode);
		}
		return p;
	}
	public static Vector shortest_path(Node start, Node end) {
		HashMap p = do_dijkstra(start, end);
		Node endprime = end;
		Vector path = new Vector();
		while (true) {
			path.add(0, (Object)endprime);
			if (endprime == start) break;
			endprime = (Node)p.get((Object)endprime);
		}
		return path;
	}
}