+1 (315) 557-6473 

Graph Data Assignment Solution using Java


Graph Data Problem

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

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

Graph Output 1

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 traveling salesman problem. This is the graph with the input information provided

Graph Output 2

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 an empty path and -1 cost.

Graph Output 3

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:

Graph Output 4

Solution:

import java.util.Arrays; import java.util.Scanner; public class hw5_1 { private static int[][] cost; private static int[] minVertices = new int[0]; private static int minCost = Integer.MAX_VALUE; public static int calculateCost(int[] vertices, int startVertex) { int totalCost = 0; int start = startVertex; for (int vertex : vertices) { if (cost[start][vertex] != -1) { totalCost += cost[start][vertex]; } else { return -1; } start = vertex; } if (cost[start][startVertex] != -1) { totalCost += cost[start][startVertex]; return totalCost; } else { return -1; } } public static void minPath(int[] vertices, int startIndex, int startVertex) { int size = vertices.length; if (size == startIndex + 1) { int pathCost = calculateCost(vertices, startVertex); if(pathCost != -1 && pathCost < minCost) { minCost = pathCost; minVertices = Arrays.copyOf(vertices, vertices.length); } } else { for (int i = startIndex; i < size; i++) { int temp = vertices[i]; vertices[i] = vertices[startIndex]; vertices[startIndex] = temp; minPath(vertices, startIndex + 1, startVertex); temp = vertices[i]; vertices[i] = vertices[startIndex]; vertices[startIndex] = temp; } } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int numVertices = scanner.nextInt(); cost = new int[numVertices][numVertices]; for (int i = 0; i < numVertices; i++) { for (int j = 0; j < numVertices; j++) { cost[i][j] = -1; } } int numValues = scanner.nextInt(); for (int i = 0; i < numValues; i++) { cost[scanner.nextInt()][scanner.nextInt()] = scanner.nextInt(); } int startVertex = scanner.nextInt(); int[] input = new int[numVertices - 1]; for (int i = 0, j = 0; i < numVertices; i++) { if (i != startVertex) { input[j] = i; j++; } } minPath(input, 0, startVertex); if(minVertices.length == 0) { System.out.println("Path:"); System.out.println("Cost:-1"); } else { System.out.print("Path:" + startVertex + "->"); for(int vertex: minVertices) { System.out.print(vertex + "->"); } System.out.println(startVertex); System.out.println("Cost:" + minCost); } } }