Page 290 - The Definitive Guide to Building Java Robots

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

CHAPTER 7 ■ NAVIGATION 271

// create room by linking regions
Room basement = new Room("shop");
basement.addEdge(a,b,new DistanceVector(190,260));
basement.addEdge(b,d,new DistanceVector(290,288));
basement.addEdge(b,c,new DistanceVector(260,216));
basement.addEdge(c,d,new DistanceVector(315,60));
basement.addEdge(d,e,new DistanceVector(280,72));
basement.addEdge(e,f,new DistanceVector(345,260));
basement.addEdge(e,g,new DistanceVector(325,200));
basement.addEdge(g,f,new DistanceVector(210,72));
return basement;

}

public ArrayList getRegions() {
return regions;
}
public ArrayList getEdges() {
return edges;
}
public void setEdges(ArrayList edges) {
this.edges = edges;
}

}
The graph that I need to navigate is almost complete. The only thing that’s missing is an
algorithm that tells the robot the shortest path to take from one vertex to another. The algo-
rithm I’ll use for that is called Dijkstra’s Algorithm (named after Edsger Dijkstra), which
determines the shortest path for a directed weighted graph.
To illustrate this example, I’ll take the following graph of the right side of the basement.
But give the weights to the graph that correspond to the distance between them.

• AB = 260
• BD = 288
• BC = 216

• CD = 60
Next, instead of imagining a robot moving between these points, let’s say we’re using
pipes and water instead. The water would be running in a line, with a constant speed.
Now, let’s put special valves at each of the vertices—B, C, and D—such that if water gets
there first from any incoming pipe, it closes the valve to all the other pipes coming into the
valve. The valve then puts up a flag saying that this vertex is the shortest path.
If you can imagine the flow of water, you can find the shortest distance, in this case the vertices
will be from A to B to C to D as the sum from BD = 288, which is greater than BC + CD = 276. See
Figure 7-13.