Page 291 - The Definitive Guide to Building Java Robots

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

272 CHAPTER 7 ■ NAVIGATION

Figure 7-13. The room graph

If you want to understand the inner workings of the algorithm more deeply than the
plumbing analogy, pick up the book A Discipline of Programming by Dijkstra himself, or check
out my reference page on it at www.scottsbots.com/definitiveguide. See Example 7-18.

Example 7-18. Dijkstra.java

package com.scottpreston.javarobot.chapter7;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;

public class Dijkstra {

private ArrayList vertices = new ArrayList();
private ArrayList edges = new ArrayList();
private HashMap oldVertex = new HashMap();
private HashMap distances = new HashMap();
private HashSet unsettled = new HashSet();
private HashSet settled = new HashSet();

public void addEdge(Edge e) {
edges.add(e);
}

public void addAllEdges(ArrayList e) {
edges = e;
}