In class today we developed the following: 

public class Vertex {
  String name; 
  public Vertex(String name) {
    this.name = name;    
  }
  public String toString() {
    return this.name;  
  }
}

import java.util.*; 

public class Neighbors extends ArrayList<Vertex> {
  public Neighbors(Vertex[] nodes) {
    for (Vertex v : nodes) 
      this.add(v); 
  }
}

import java.util.*; 

public class Path extends ArrayList<Vertex> {
  public Path() {
    
  }
  public Path(Vertex v) {
    this.add( v ); 
  }
  public Path clone() {
    Path c = new Path();
    for (Vertex v : this)
      c.add(v);
    return c; 
  }
}

import java.util.*; 

public class Paths extends ArrayList<Path> {
  public Paths() {
    
  }
  public Paths(Path p) {
    this.add( p ); 
  }
}

import java.util.*; 

public class Graph extends HashMap<Vertex, Neighbors> {
  public static Graph g = new Graph(); 
  public static Neighbors neighborsOf(Vertex v) {
    return Graph.g.get(v);
  }  
  public Path shortestPath(Vertex stop, 
                           Paths candidates) {
    if (candidates == null) return null;
    else if (candidates.size() == 0) return new Path();
    else {
      for (Path c : candidates)
        if (c.get(c.size() - 1) == stop) 
          return c; 
      // extends the candidates and keep searching
      Paths p = new Paths(); 
      for (Path c : candidates) {
        Vertex last = c.get(c.size() - 1); 
        Neighbors n = Graph.neighborsOf(last);
        for (Vertex v : n) {
          Path np = c.clone();
          if (p.contains(v)) { }
          else { 
            np.add(v); 
            p.add(np);
          }
        }
        return shortestPath(start, p); 
      }
      return null; 
    }
  }
  
  public static void main(String[] args) {
    // Graph.g = new Graph(); 
    Vertex  sf = new Vertex("San Francisco");
    Vertex   p = new Vertex("Portland");
    Vertex   s = new Vertex("Seattle");
    Vertex   v = new Vertex("Vancouver");
    Vertex   c = new Vertex("Calgary");
    Vertex   h = new Vertex("Helena");
    Vertex slc = new Vertex("Salt Lake City");
    Vertex  la = new Vertex("Los Angeles");
    Vertex  lv = new Vertex("Las Vegas");
    Vertex  ph = new Vertex("Phoenix");
    Vertex  ep = new Vertex("El Paso");
    Vertex   d = new Vertex("Duluth");
    Vertex   o = new Vertex("Omaha");
    Vertex  de = new Vertex("Denver");
    Vertex sfe = new Vertex("Santa Fe");
    Vertex dal = new Vertex("Dallas");

    Graph.g.put(sf, new Neighbors(new Vertex[] { p, la, slc })); 
    // an alternative would have been to add/set the neighbors to the vertex
    // however if a vertext belongs to more than one map (Delta, Southwest, American Airlines, etc.) that would become a problem    

    System.out.println( g ); 
    
    Path a1 = g.shortestPath(p, null); // new Paths(new Path(sf)));
    System.out.println( a1 );
    Path a2 = g.shortestPath(p, new Paths()); // new Paths(new Path(sf)));
    System.out.println( a2 );
    Path a3 = g.shortestPath(p, new Paths(new Path(sf)));
    System.out.println( a3 );
    Path a4 = g.shortestPath(sf, new Paths(new Path(sf)));
    System.out.println( a4 );
    
  }
}