Dijkstra

From :http://www.cs.bgu.ac.il/~vassilii/forth-opt/Dijkstra_8java-source.html
Dijkstra.java Go to the documentation of this file.
00001 // $Header: /home/vassilii/BGU/courses/fp042/forth-opt/RCS/Dijkstra.java,v 2.0 2004/09/05 00002
00003 import java.util.*;
00004
00005 public class Dijkstra implements PathFinder {
00006
00007 public Iterator findShortestPath(Vertex source, Vertex destination) {
00008 Map s = new HashMap();
00009 PriorityQueueSet q = new PriorityQueueSet();
00010 q.enqueue(source, 0, null);
00011
00012 while (!q.isEmpty()) {
00013 //u <- extract-min(q)
00014 Element u = q.dequeue();
00015 if (u.vertex.equals(destination)) return extractPath(u, s);
00016 // s <- s U {u}
00017 s.put(u.vertex, u);
00018 for (Iterator iter = u.vertex.outgoingEdges(destination); iter.hasNext();) {
00019 Edge e = (Edge) iter.next();
00020 Vertex v = e.destination();
00021 if (!s.containsKey(v))
00022 q.enqueue(v, u.distance + e.weight(), e);
00023 }
00024 }
00025 return new ArrayList().iterator(); // empty for no path found
00026 }
00027
00028 static private Iterator extractPath(Element elm, Map s) {
00029 LinkedList l = new LinkedList();
00030
00031 for (Edge e = elm.previous; e != null; e = ((Element)s.get(e.source())).previous)
00032 l.addFirst(e);
00033 return l.iterator();
00034 }
00035
00036 static class PriorityQueueSet {
00037 SortedSet q = new TreeSet();
00038 Map lookUp = new HashMap();
00039
00044 public void enqueue(Vertex v, int d, Edge e) {
00045 if (!lookUp.containsKey(v)) {
00046 Element elm = new Element(v, d, e);
00047 lookUp.put(v, elm);
00048 q.add(elm);
00049 } else {
00050 Element elm = (Element)lookUp.get(v);
00051 if (elm.distance > d) {
00052 q.remove(elm);
00053 elm.distance = d;
00054 elm.previous = e;
00055 q.add(elm);
00056 }
00057 }
00058 }
00059
00064 public Element dequeue() {
00065 if (q.isEmpty()) return null;
00066 Element elm = (Element)q.first();
00067 q.remove(elm);
00068 lookUp.remove(elm.vertex);
00069 return elm;
00070 }
00071
00072 public boolean isEmpty() { return q.isEmpty(); }
00073
00074 public String toString() { return q.toString(); }
00075 }
00076
00077 static class Element implements Comparable {
00078 final Vertex vertex;
00079 int distance;
00080 Edge previous;
00081
00082 public Element(Vertex v, int d, Edge e) {
00083 this.vertex = v;
00084 this.distance = d;
00085 this.previous = e;
00086 }
00087
00088 public int compareTo(Object o) {
00089 Element k = (Element)o;
00090 if (k.distance == this.distance)
00091 return this.vertex.compareTo(k.vertex);
00092 else
00093 return this.distance - k.distance;
00094 }
00095
00096 public boolean equals(Object o) {
00097 Element k = (Element)o;
00098 return this.distance == k.distance && this.vertex.equals(k.vertex);
00099 }
00100
00101 public String toString() {
00102 return "["+vertex+","+distance+","+previous+"]";
00103 }
00104 }
00105 }
Generated on Tue Sep 21 21:39:11 2004 for FORTH stack optimization by 1.3.8