Question

IN JAVA

A salesman wants to go to five different cities and sell some products. The locations of the cities are listed in the following table.

City #	X_location	Y_location
City 1	1	1
City 2	1	3
City 3	4	1
City 4	5	3
City 5	3	5

The distance between two cities is defined as the Euclidean distance. That is:

Distance = sqrt( (x1 – x2)^2 + (y1 – y2)^2 )

For example, the distance between cities 1 and 2 will be:

Distance = sqrt( (1 – 1)^2 + (1 – 3)^2 ) = sqrt( 4 ) = 2

The purpose: The salesman starts his journey from city 1. He then has 4 remaining options for the next city (city 2, city 3, city 4, city 5). If he chooses city 3 as the next destination, then he will have 3 remaining options (city 2, city 4, city 5). He wants to travel all the cities and then come back to the start location (City 1). Not all the paths will be a good choice. We want to help the salesman by finding the shortest path (best order of cities to visit (visit all of them once) starting from city 1).

Steps:

Step 1 [7 points]: Create a class City with x and y as the class variables. The constructor with argument will get x and y and will initialize the city. Add a member function getDistanceFrom() to the class that gets a city as the input and finds the distance between the two cities.

city1.getDistanceFrom(city2) will be distance between city 1 and 2.

Step 2 [6 points]: Create 5 city objects and initialize their location (x and y) using the above table. Then put all of the five cities in a vector.

Step 3 [7 points]: Create a two dimensional array or vector DistanceVec of size 5 * 5 and initialize it such that DistanceVec[i,j] is the distance between city_i and city_j. Print the distanceVec and show the distance among all cities.

Step 4 [15 points]: If the salesman starts from the city 1, search all the possible paths and find the optimal path (order of cities to visit) that leads to the minimum total travel distance. Display the found optimal path (order of cities to travel) in your sample run.

Answer 1

import java.lang.Math;
import java.util.Stack;
import java.util.Vector;

public class City {
    public int x;
    public int y;

    public City(int x,int y){
        this.x = x;
        this.y = y;
    }

    double getDistanceFrom(City c){
        int x2 = c.x;
        int y2 = c.y;
        double d = Math.sqrt((x-x2)*(x-x2) + (y-y2)*(y-y2));
        return d;
    }

    public void findOptimalSolution(double dvec[][])
    {
        Stack<Integer> stack = new Stack<Integer>();
        int cities = dvec.length;
        System.out.println("Number of cities = " + cities);
        int[] visited = new int[cities + 1];
        visited[1] = 1;
        stack.push(1);
        int element;
        int distance = 0;
        int i;
        boolean foundPath = false;
        System.out.print(1 + "\t");

        while (!stack.isEmpty()){
            element = stack.peek();
            i = 1;
            double min = -1;
            while (i <= cities){
                if (dvec[element-1][i-1] > 1 && visited[i] == 0){
                    if (min == -1 || min > dvec[element-1][i-1]){
                        min = dvec[element-1][i-1];
                        distance = i;
                        foundPath = true;
                    }
                }
                i++;
            }
            if (foundPath){
                visited[distance] = 1;
                stack.push(distance);
                System.out.print(distance + "\t");
                foundPath = false;
                continue;
            }
            stack.pop();
        }
    }

    public static void main(String[] args){

        City city1 = new City(1,1);
        City city2 = new City(1,3);
        City city3 = new City(4,1);
        City city4 = new City(5,3);
        City city5 = new City(3,5);

        Vector<City> cityVector = new Vector<City>();

        cityVector.add(city1);
        cityVector.add(city2);
        cityVector.add(city3);
        cityVector.add(city4);
        cityVector.add(city5);

        double[][] DistanceVec = new double[5][5];

        for(int i=0;i<5;i++){
            for(int j=i;j<5;j++){
                City c1 = cityVector.get(i);
                City c2 = cityVector.get(j);
                DistanceVec[i][j] = c1.getDistanceFrom(c2);
                DistanceVec[j][i] = DistanceVec[i][j];
            }
        }

        System.out.println("Printing the DistanceVec \n");
        for(int i=0;i<5;i++){
            for(int j=0;j<5;j++){
                System.out.print("" + DistanceVec[i][j] + "\t");
            }
            System.out.println();
        }

        city1.findOptimalSolution(DistanceVec);

    }

}

Output:

Please appreciate the solution if you find it helpful.

If you have any doubts in the solution, feel free to ask me in the comment section.