Question

Write a C++ or Java program that reads an input graph data from a user. Then, it should present a path for the travelling salesman problem (TSP). In the assignment, you can assume that the maximum number ofvertices in the input graph is less than or equal to 20.

Input format: This is a sample input from a user.

4 12 0 1 2 0 3 7 0 2 5 1 0 2 1 2 8 1 3 3 2 0 5 2 1 8 2 3 1 3 0 7 3 1 9 3 2 1 0

The first line (= 4 in the example) indicates that there are four vertices in the graph. The next line (= 12 in the example) indicates the number of edges in the graph. The remaining 12 lines are the edge information with the “source vertex”, “destination vertex”, and “cost”. The last line (= 0 in the example) indicates the starting vertex of the travelling salesman problem. This is the graph with the input information provided.

Sample Run 0: Assume that the user typed the following lines

4

12

0 1 2

0 3 7

0 2 5

1 0 2

1 2 8

1 3 3

2 0 5

2 1 8

2 3 1

3 0 7

3 1 9

3 2 1

0

This is the correct output. Your program should present the path and total cost in separate lines.

Path:0->1->3->2->0

Cost:11

Sample Run 1: Assume that the user typed the following lines

5

6

0 2 7

3 1 20

0 4 3

1 0 8

2 4 100

3 0 19

3

This is the correct output.

Path:

Cost:-1

Note that if there is no path for the TSP, your program should present empty path and -1 cost.

Sample Run 2: Assume that the user typed the following lines

5

7

0 2 8

2 1 7

2 4 3

1 4 100

3 0 20

3 2 19

4 3 50

3

This is the correct output of your program.

Path:3->0->2->1->4->3

Cost:185

This is the directed graph of the input data:

[Hint]: To solve this problem, you can use all permutations of the vertices, except the starting vertex. For example, there are three vertices 1, 2, and 3, in the first sample run, except the starting vertex 0. This is all permutations with the three vertices

            1, 2, 3

            1, 3, 2

            2, 1, 3,

            2, 3, 1

            3, 1, 2

            3, 2, 1

Answer 1

import java.util.*;
class Main
{ 

        // Function to find the minimum weight 
        // Hamiltonian Cycle 
        static int tsp(int[][] graph, boolean[] g, 
                                int Pos, int n, 
                                int cnt, int cost, int res) 
        { 

                
                // Finally return to check for more possible values 
                if (cnt == n && graph[Pos][0] > 0) 
                { 
                        res = Math.min(res, cost + graph[Pos][0]); 
         
                        return res; 
                } 

                for (int i = 0; i < n; i++) 
                { 
                        if (g[i] == false && graph[Pos][i] > 0) 
                        { 

                        
                                g[i] = true; 
                                res = tsp(graph, g, i, n, cnt + 1, 
                                                cost + graph[Pos][i], res); 

                                
                                g[i] = false; 
                        } 
                } 
    
                return res; 
        } 

        // Driver code 
        public static void main(String[] args) 
        { Scanner s=new Scanner(System.in);

                // n is the number of nodes i.e. V 
                int n = 4; 

                int[][] graph = {{0, 2, 5, 7}, 
                                                {2, 0, 8, 3}, 
                                                {5, 8, 0, 1}, 
                                                {7, 9, 1, 0}}; 

                // Boolean array to check if a node 
                // has been visited or not 
                boolean[] g = new boolean[n]; 

                // Mark 0th node as visited 
                g[0] = true; 
                int res = Integer.MAX_VALUE; 

                // Find the minimum weight Hamiltonian Cycle 
                res = tsp(graph, g, 0, n, 1, 0, res); 

                // res is the minimum weight Hamiltonian Cycle 
                System.out.println(res); 
        } 
}