1  public class TestShortestPath {
  2    public static void main(String[] args) {
  3      String[] vertices = {"Seattle", "San Francisco", "Los Angeles",
  4        "Denver", "Kansas City", "Chicago", "Boston", "New York",
  5        "Atlanta", "Miami", "Dallas", "Houston"};
  6  
  7      int[][] edges = {
  8        {0, 1, 807}, {0, 3, 1331}, {0, 5, 2097},
  9        {1, 0, 807}, {1, 2, 381}, {1, 3, 1267},
 10        {2, 1, 381}, {2, 3, 1015}, {2, 4, 1663}, {2, 10, 1435},
 11        {3, 0, 1331}, {3, 1, 1267}, {3, 2, 1015}, {3, 4, 599}, 
 12          {3, 5, 1003},
 13        {4, 2, 1663}, {4, 3, 599}, {4, 5, 533}, {4, 7, 1260},
 14          {4, 8, 864}, {4, 10, 496},
 15        {5, 0, 2097}, {5, 3, 1003}, {5, 4, 533}, 
 16          {5, 6, 983}, {5, 7, 787},
 17        {6, 5, 983}, {6, 7, 214},
 18        {7, 4, 1260}, {7, 5, 787}, {7, 6, 214}, {7, 8, 888},
 19        {8, 4, 864}, {8, 7, 888}, {8, 9, 661}, 
 20          {8, 10, 781}, {8, 11, 810},
 21        {9, 8, 661}, {9, 11, 1187},
 22        {10, 2, 1435}, {10, 4, 496}, {10, 8, 781}, {10, 11, 239},
 23        {11, 8, 810}, {11, 9, 1187}, {11, 10, 239}
 24      };
 25  
 26      WeightedGraph<String> graph1 = 
 27        new WeightedGraph<>(vertices, edges);
 28      WeightedGraph<String>.ShortestPathTree tree1 = 
 29        graph1.getShortestPath(graph1.getIndex("Chicago"));
 30      tree1.printAllPaths();
 31  
 32      // Display shortest paths from Houston to Chicago
 33      System.out.print("Shortest path from Houston to Chicago: ");
 34      java.util.List<String> path 
 35        = tree1.getPath(graph1.getIndex("Houston"));
 36      for (String s: path) {
 37        System.out.print(s + " ");
 38      }
 39  
 40      edges = new int[][] {
 41        {0, 1, 2}, {0, 3, 8}, 
 42        {1, 0, 2}, {1, 2, 7}, {1, 3, 3},
 43        {2, 1, 7}, {2, 3, 4}, {2, 4, 5},
 44        {3, 0, 8}, {3, 1, 3}, {3, 2, 4}, {3, 4, 6},
 45        {4, 2, 5}, {4, 3, 6}
 46      };
 47      WeightedGraph<Integer> graph2 = new WeightedGraph<>(edges, 5);
 48      WeightedGraph<Integer>.ShortestPathTree tree2 = 
 49        graph2.getShortestPath(3); // Get shortest path from 3
 50      System.out.println("\n");
 51      tree2.printAllPaths();
 52    }
 53  }