public class TravelingSalesmanPaths
1: //TravelingSalemanPaths.java
3: import java.util.ArrayList;
5: public class TravelingSalesmanPaths
6: {
7: public static final int NUM_CITIES = 3; // Number of cities
8: // Distance between cities
9: public static int[][] cityDistances = new int[NUM_CITIES][NUM_CITIES];
10: public static String[] cityNames = new String[NUM_CITIES]; // City names
12: /* Output every possible travel path.
13: Each recursive call moves to a new city.
14: */
15: public static void travelPaths
16: (
17: ArrayList<Integer> currPath,
18: ArrayList<Integer> needToVisit
19: )
20: {
21: int totalDist; // Total distance given current path
22: int tmpCity; // Next city distance
23: int i; // Loop index
25: if (currPath.size() == NUM_CITIES) // Base case: Visited all cities
26: {
27: totalDist = 0; // Return total path distance
28: for (i = 0; i < currPath.size(); ++i)
29: {
30: System.out.print(cityNames[currPath.get(i)] + " ");
32: if (i > 0)
33: {
34: totalDist +=
35: cityDistances[currPath.get(i - 1)][currPath.get(i)];
36: }
37: }
39: System.out.println("= " + totalDist);
40: }
41: else // Recursive case: pick next city
42: {
43: for (i = 0; i < needToVisit.size(); ++i)
44: {
45: // add city to travel path
46: tmpCity = needToVisit.get(i);
47: needToVisit.remove(i);
48: currPath.add(tmpCity);
50: travelPaths(currPath, needToVisit);
52: // remove city from travel path
53: needToVisit.add(i, tmpCity);
54: currPath.remove(currPath.size() - 1);
55: }
56: }
57: }
59: public static void main(String[] args)
60: {
61: ArrayList<Integer> needToVisit = new
62: ArrayList<Integer>(); // Cities left to visit
63: ArrayList<Integer> currPath = new
64: ArrayList<Integer>(); // Current path traveled
66: // Initialize distances array
67: cityDistances[0][0] = 0;
68: cityDistances[0][1] = 960; // Boston-Chicago
69: cityDistances[0][2] = 2960; // Boston-Los Angeles
70: cityDistances[1][0] = 960; // Chicago-Boston
71: cityDistances[1][1] = 0;
72: cityDistances[1][2] = 2011; // Chicago-Los Angeles
73: cityDistances[2][0] = 2960; // Los Angeles-Boston
74: cityDistances[2][1] = 2011; // Los Angeles-Chicago
75: cityDistances[2][2] = 0;
77: cityNames[0] = "Boston";
78: cityNames[1] = "Chicago";
79: cityNames[2] = "Los Angeles";
80: /*
81: needToVisit.add(new Integer(0)); // Boston
82: needToVisit.add(new Integer(1)); // Chicago
83: needToVisit.add(new Integer(2)); // Los Angeles
84: */
85: needToVisit.add(0); // Boston
86: needToVisit.add(1); // Chicago
87: needToVisit.add(2); // Los Angeles
89: // Explore different paths
90: travelPaths(currPath, needToVisit);
91: }
92: }