Java Program to Solve TSP Using Minimum Spanning Trees

This is a java program to solve TSP using MST.

Here is the source code of the Java Program to Solve TSP Using Minimum Spanning Trees. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

package com.maixuanviet.hardgraph;
 
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class TSPUsingMST
{
    // Arrays to keep track of info. related to each city
    private String[]   cityName;
    private String[]   cityState;
    private int[]      cityLat;
    private int[]      cityLong;
    private int[]      cityPop;
    // 2-D array to keep track of pairwise distances between cities
    private int[][]    distances;
    // number of cities
    private static int numCities;
 
    public TSPUsingMST(int n)
    {
        numCities = n;
        // Allotting the space for each 1-D array
        cityName = new String[numCities];
        cityState = new String[numCities];
        cityLat = new int[numCities];
        cityLong = new int[numCities];
        cityPop = new int[numCities];
        // Allocate space for each 2-D array. These arrays have 0 elements in
        // row 0,
        // 1 element in row 1, 2 elements in row 2, etc.
        distances = new int[numCities][];
        for (int i = 0; i < numCities; i++)
            distances[i] = new int[i];
        try
        {
            // Construct a buffered reader object and connect it to the files
            // "miles.dat"
            BufferedReader in = new BufferedReader(new FileReader("miles.dat"));
            // A counter that keeps track of the index of the current city being
            // read
            int cityNumber = 0;
            // While-loop for reading in data from "miles.dat." At the beginning
            // of the while-loop
            // the expectation is that we'll be reading a line containing the
            // city name. Instead,
            // if we encounter a line that starts with "*" then we skip to the
            // next line
            while (cityNumber < numCities)
            {
                // Read in a line
                String line = in.readLine();
                // Skip the rest of the loop if line starts with a "*"
                if (line.charAt(0) == '*')
                    continue;
                // Otherwise tokenize the line
                StringTokenizer tokenizedLine = new StringTokenizer(line, ",[]");
                // Putting actual data into correct position in the array
                cityName[cityNumber] = tokenizedLine.nextToken();
                cityState[cityNumber] = (tokenizedLine.nextToken()).trim(); // trim()
                                                                            // gets
                                                                            // rid
                                                                            // of
                                                                            // leading/trailing
                                                                            // blanks
                cityLat[cityNumber] = Integer.parseInt(tokenizedLine
                        .nextToken());
                cityLong[cityNumber] = Integer.parseInt(tokenizedLine
                        .nextToken());
                cityPop[cityNumber] = Integer.parseInt(tokenizedLine
                        .nextToken());
                // while loop to put distances in the array; this may need to
                // read several lines
                int mileNumber = 0;
                while (mileNumber < cityNumber)
                {
                    // Read a mileage line and tokenize it
                    String mileage = in.readLine();
                    StringTokenizer tokenizedMileage = new StringTokenizer(
                            mileage, " ");
                    // Read all the mileage data in this line into row
                    // cityNumber; increment
                    // mileNumber after each read
                    while (tokenizedMileage.hasMoreTokens())
                    {
                        distances[cityNumber][cityNumber - mileNumber - 1] = Integer
                                .parseInt(tokenizedMileage.nextToken());
                        mileNumber++;
                    }
                } // end of while reading distances
                cityNumber++;
            } // end of while reading cities
            in.close();
        } // end of try
        catch (IOException e)
        {
            System.out.println("File not found.");
        }
    } // end of TSPTester() constructor
 
    // A simple getIndex method to help test the constructor
    int getIndex(String city, String state)
    {
        int location;
        for (location = 0; location < numCities; location++)
            if ((cityName[location].equals(city))
                    && (cityState[location].equals(state)))
                return location;
        return -1;
    }
 
    // Print information about a city, given a city index
    void printCityInfo(int index)
    {
        System.out
                .println(cityName[index] + " " + cityState[index] + " "
                        + cityLat[index] + " " + cityLong[index] + " "
                        + cityPop[index]);
    }
 
    // Print distance information between a given pair of cities
    void printDistanceInfo(int i, int j)
    {
        if (i < j)
            System.out.println(distances[j][i]);
        else
            System.out.println(distances[i][j]);
    }
 
    int getDistance(int i, int j)
    {
        if (i < j)
            return distances[j][i];
        else if (j < i)
            return distances[i][j];
        else
            return 0;
    }
 
    int[] greedyTSP()
    {
        // Find a cheapest triangle
        // Load triangle 0-1-2 into the the first 3 slots of the greedy array
        int[] greedy = new int[numCities];
        int currentDistance;
        greedy[0] = 0;
        greedy[1] = 1;
        greedy[2] = 2;
        int currentBestDistance = getDistance(0, 1) + getDistance(1, 2)
                + getDistance(2, 0);
        for (int i = 0; i < numCities; i++)
            for (int j = 0; j < i; j++)
                for (int k = 0; k < j; k++)
                    if ((currentDistance = getDistance(i, j)
                            + getDistance(j, k) + getDistance(i, k)) < currentBestDistance)
                    {
                        greedy[0] = i;
                        greedy[1] = j;
                        greedy[2] = k;
                        currentBestDistance = currentDistance;
                    }
        // Try greedily to add a city that yields the smallest increase
        // in the cost of the tour
        int partialTourSize = 3;
        boolean[] visited = new boolean[numCities];
        for (int i = 0; i < numCities; i++)
            visited[i] = false;
        visited[greedy[0]] = true;
        visited[greedy[1]] = true;
        visited[greedy[2]] = true;
        // Main loop: keep repeating until partial tour covers all cities
        while (partialTourSize < numCities)
        {
            int smallestIncrease = Integer.MAX_VALUE;
            int increase = 0;
            int bestInsertionPoint = 0;
            int bestCity = 0;
            // Scan through all cities, stopping at unvisited cities
            for (int i = 0; i < numCities; i++)
            {
                if (!visited[i])
                {
                    // Consider all possible positions of inserting city i into
                    // the tour
                    // and record the smallest increase
                    for (int j = 0; j < partialTourSize; j++)
                    {
                        increase = getDistance(greedy[j], i)
                                + getDistance(i, greedy[(j + 1) % numCities])
                                - getDistance(greedy[j], greedy[(j + 1)
                                        % numCities]);
                        if (increase < smallestIncrease)
                        {
                            smallestIncrease = increase;
                            bestCity = i;
                            bestInsertionPoint = j;
                        } // end of if we have found a smaller increase
                    } // end of for-j
                } // end of if not visited
            } // end of for-i
              // Now we are ready to insert the bestCity at the bestInsertionPoint
            for (int j = partialTourSize - 1; j > bestInsertionPoint; j--)
                greedy[j + 1] = greedy[j];
            greedy[bestInsertionPoint + 1] = bestCity;
            visited[bestCity] = true;
            partialTourSize++;
        } // end-while
        return greedy;
    }
 
    void copy(int[] source, int[] dest)
    {
        for (int i = 0; i < dest.length; i++)
            dest[i] = source[i];
    }
 
    void TSP(int[] R, int partialTourSize, boolean[] visited, int[] T)
    {
        // Base case: we have discovered a tour better than T
        if ((partialTourSize == numCities) && (cost(R) < cost(T)))
        {
            System.out.println("Base case. Tour cost is " + cost(R));
            copy(R, T);
            return;
        }
        // Another base case: our partial tour is not worth completing
        if (cost(R, partialTourSize) >= cost(T))
            return;
        // Recursive case: R is not complete and is currently better than T
        // and is therefore worth completing
        for (int i = 0; i < numCities; i++)
        {
            if (!visited[i])
            {
                // System.out.println("Appending " + i);
                visited[i] = true;
                R[partialTourSize++] = i;
                TSP(R, partialTourSize, visited, T);
                partialTourSize--;
                visited[i] = false;
                // System.out.println("Deleting " + i);
            }
        } // end of for-loop
    } // end of TSP
 
    double cost(int[] tour)
    {
        return cost(tour, tour.length);
    }
 
    double cost(int[] tour, int tourSize)
    {
        double c = 0;
        for (int i = 0; i < tourSize - 1; i++)
            c = c + getDistance(tour[i], tour[i + 1]);
        c = c + getDistance(tour[tourSize - 1], tour[0]);
        return c;
    }
 
    // Main method
    public static void main(String[] args)
    {
        int n = 15;
        TSPUsingMST T = new TSPUsingMST(n);
        // Initialize the list of vertices in the tree
        // Initially, no one except vertex 0 is in the tree
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++)
            visited[i] = false;
        visited[0] = true;
        // Initialize the int[] that maintains the tree to default values
        // No vertices have parents set, except vertex 0 whose parent is itself
        int[] tree = new int[n];
        for (int i = 0; i < n; i++)
            tree[i] = -1;
        tree[0] = 0;
        for (int i = 1; i <= n - 1; i++)
        {
            long minWeight = Long.MAX_VALUE;
            int bestVertex = -1;
            int bestParent = -1;
            for (int j = 0; j < n; j++)
            {
                for (int k = 0; k < n; k++)
                {
                    if ((visited[j]) && (!visited[k]))
                    {
                        if (T.getDistance(j, k) < minWeight)
                        {
                            minWeight = T.getDistance(j, k);
                            bestVertex = k;
                            bestParent = j;
                        } // end if better distance is found
                    } // end if an edge between a visited and an unvisited is
                      // found
                } // end for-k
            } // end for-j
              // Update visited and tree
            visited[bestVertex] = true;
            tree[bestVertex] = bestParent;
        } // end for-i
          // Printing the MST
        for (int i = 1; i < n; i++)
            System.out.println(T.cityName[i] + " " + T.cityState[i] + ", "
                    + T.cityName[tree[i]] + " " + T.cityState[tree[i]]);
        // Compting the MST cost
        long cost = 0;
        for (int i = 0; i < n; i++)
            cost += T.getDistance(i, tree[i]);
        System.out.println("The cost of the minimum spanning tree is " + cost);
    } // end main method
} // end class

Output:

$ javac TSPUsingMST.java
$ java TSPUsingMST
 
Yankton SD, Wisconsin Dells WI
Yakima WA, Williston ND
Worcester MA, Wilmington DE
Wisconsin Dells WI, Youngstown OH
Winston-Salem NC, Winchester VA
Winnipeg MB, Yankton SD
Winchester VA, Wilmington DE
Wilmington NC, Winston-Salem NC
Wilmington DE, Williamsport PA
Williston ND, Winnipeg MB
Williamsport PA, Youngstown OH
Williamson WV, Winston-Salem NC
Wichita Falls TX, Wichita KS
Wichita KS, Yankton SD
The cost of the minimum spanning tree is 5461

Related posts:

Cài đặt và sử dụng Swagger UI
Java Program to Find the Edge Connectivity of a Graph
Spring Data – CrudRepository save() Method
Error Handling for REST with Spring
A Guide to the ResourceBundle
Java Program to Implement Circular Singly Linked List
Java Program to Generate All Possible Subsets with Exactly k Elements in Each Subset
Java Program to Implement RoleList API
Chuyển đổi Array sang ArrayList và ngược lại
Java Scanner hasNext() vs. hasNextLine()
Quick Guide to java.lang.System
Java Program to Perform Right Rotation on a Binary Search Tree
Java Convenience Factory Methods for Collections
String Processing with Apache Commons Lang 3
Java List UnsupportedOperationException
Introduction to Java Serialization
Returning Custom Status Codes from Spring Controllers
Spring Boot - Enabling Swagger2
Java Program to Implement Control Table
Converting between an Array and a List in Java
Guide to java.util.Formatter
How to Get the Last Element of a Stream in Java?
@DynamicUpdate with Spring Data JPA
Mapping a Dynamic JSON Object with Jackson
Loại bỏ các phần tử trùng trong một ArrayList như thế nào trong Java 8?
Sao chép các phần tử của một mảng sang mảng khác như thế nào?
Using a Spring Cloud App Starter
Checking for Empty or Blank Strings in Java
Kết hợp Java Reflection và Java Annotations
Java Stream Filter with Lambda Expression
Java Program to Create a Minimal Set of All Edges Whose Addition will Convert it to a Strongly Conne...
Java Program to Check if a Given Graph Contain Hamiltonian Cycle or Not