Page 293 - The Definitive Guide to Building Java Robots

Preston_5564C07.fm Page 274 Monday, September 26, 2005 5:38 AM

274 CHAPTER 7 ■ NAVIGATION

public Vertex extractMinimum() {
Iterator i = unsettled.iterator();
int min = Integer.MAX_VALUE;
Vertex minV = null;
while (i.hasNext()) {
Vertex tmp = (Vertex) i.next();
if (getShortDistance(tmp) < min) {
min = getShortDistance(tmp);
minV = tmp;
}
}
unsettled.remove(minV);
return minV;
}

public void relaxNeighbors(Vertex u) {
int[][] adj = getAdj();
int size = vertices.size();
for (int i = 0; i < size; i++) {
Vertex vi = (Vertex) vertices.get(i);
if (vi.equals(u)) { // only check this i'th column
for (int j = 0; j < size; j++) {
Vertex v = (Vertex) vertices.get(j);
int w2 = adj[i][j];
// should give all adjacent vertices not settled
if (w2 > 0 && w2 < Integer.MAX_VALUE
&& (settled.contains(v) == false)) {
// does a shorter distance exist?
if (getShortDistance(v) > getShortDistance(u)
+ getDist(u, v)) {
int d = getShortDistance(u) + getDist(u, v);
setShortDistance(v, d);
setPred(v,u);
}
}

}
}

}
}

public ArrayList getShortestPath( Vertex start, Vertex end) {
unsettled.add(start);
setShortDistance(start,0);
while (unsettled.size() > 0) {