/* Dijkstra's algorithm for the single-source shortest path problem * in an undirected graph whose edges have integer weights. */ public class Dijkstra { /** Infinity value. */ public static final int INFINITE = Integer.MAX_VALUE; /** Input graph. */ protected Graph graph; /** Decoration key for edge weights */ protected Object WEIGHT; /** Auxiliary priority queue. */ protected AdaptablePriorityQueue Q; /** Executes Dijkstra's algorithm. * @param g Input graph * @param s Source vertex * @param w Weight decoration object */ public void execute(Graph g, Vertex s, Object w) { graph = g; WEIGHT = w; Q = new HeapAdaptablePriorityQueue(new DefaultComparator()); dijkstraVisit(s); } /** Get the distance of a vertex from the source vertex. * @param u Start vertex for the shortest path tree */ public int getDist(Vertex u) { return ((Integer) u.get(DIST)).intValue(); }