/* Dijkstra 1. Map (n1, n2) -> distance 2. Queue (position, distance) */ public class Paire { public int node1, node2; public Paire (int n1, n2) { node1 = n1; node2 = n2; } public hashCode () { return node1 ^ (node2*42); } public equals (Object o) { if (!(o instanceof Paire)) return false; return ((o.node1 == node1) && (o.node2 == node2)); } } public class SearchPosition implements Comparable { int node; double distance; public SearchPosition (int node, double distance) { this.node = node; this.distance = distance; } public int compareTo (Object o) { SearchPosition other = (SearchPosition) o; if (distance == other.distance) return node < other.node; return distance < other.distance; } } void dijkstra(Map distances, int origine, int destination) { PriorityQueue queue; queue.add(new SearchPosition(origine, 0)); while (true) { SearchPosition next = queue.remove(); if (next.node == destination) return; for (int i = origine; i < destination; i++) { Double dist = distances.get(new Paire(next.node, i)); if (null == dist) continue; queue.add(new SearchPosition(i, next.distance+dist)); } } }