Find centralized, trusted content and collaborate around the technologies you use most.
Learn more about CollectivesStack Internal
Knowledge at work
Bring the best of human thought and AI automation together at your work.
Explore Stack Internal distMtxdistMtx stores all the intercity distances, and distances are symmetric, meaning if distance from city A to city B is 3, then the distance from city B to city A is also 3. Also, if two cities don't have any direct paths, the distance value is -1.
The main function reads the intercity distances from a text file. Because I'm assuming the number of cities will always be less than 100, global int variable distMindistMtx is [100][100].
distMtx stores all the intercity distances, and distances are symmetric, meaning if distance from city A to city B is 3, then the distance from city B to city A is also 3. Also, if two cities don't have any direct paths, the distance value is -1.
The main function reads the intercity distances from a text file. Because I'm assuming the number of cities will always be less than 100, global int variable distMin is [100][100].
distMtx stores all the intercity distances, and distances are symmetric, meaning if distance from city A to city B is 3, then the distance from city B to city A is also 3. Also, if two cities don't have any direct paths, the distance value is -1.
The main function reads the intercity distances from a text file. Because I'm assuming the number of cities will always be less than 100, global int variable distMtx is [100][100].
Edit:
The main function reads the intercity distances from a text file. Because I'm assuming the number of cities will always be less than 100, global int variable distMin is [100][100].
Once the matrix is filled with the necessary information, an array of all the cities are created. The names of the cities are basically numbers. So if I have 4 cities, set[4] = {0, 1, 2, 3}.
In the main function, after distMtx and set is created, first call to compute() is called:
int optRoute = compute(set, 0); System.out.println(optRoute); Sample input:
-1 3 2 7 3 -1 10 1 2 10 -1 4 7 1 4 -1 Expected output:
10 Edit:
The main function reads the intercity distances from a text file. Because I'm assuming the number of cities will always be less than 100, global int variable distMin is [100][100].
Once the matrix is filled with the necessary information, an array of all the cities are created. The names of the cities are basically numbers. So if I have 4 cities, set[4] = {0, 1, 2, 3}.
In the main function, after distMtx and set is created, first call to compute() is called:
int optRoute = compute(set, 0); System.out.println(optRoute); Sample input:
-1 3 2 7 3 -1 10 1 2 10 -1 4 7 1 4 -1 Expected output:
10 I'm a beginner, and I'm trying to write a working travelling salesman problem using dynamic programming approach.
This is the code for my compute function:
public static int compute(int[] unvisitedSet, int dest) { if (unvisitedSet.length == 1) return distMtx[dest][unvisitedSet[0]]; int[] newSet = new int[unvisitedSet.length-1]; int distMin = Integer.MAX_VALUE; for (int i = 0; i < unvisitedSet.length; i++) { for (int j = 0; j < newSet.length; j++) { if (j < i) newSet[j] = unvisitedSet[j]; else newSet[j] = unvisitedSet[j+1]; } int distCur; if (distMtx[dest][unvisitedSet[i]] != -1) { distCur = compute(newSet, unvisitedSet[i]) + distMtx[unvisitedSet[i]][dest]; if (distMin > distCur) distMin = distCur; } else { System.out.println("No path between " + dest + " and " + unvisitedSet[i]); } } return distMin; } The code is not giving me the correct answers, and I'm trying to figure out where the error is occurring. I think my error occurs when I add: distCur = compute(newSet, unvisitedSet[i]) + distMtx[unvisitedSet[i]][dest]; So I've been messing around with that part, moving the addition to the very end right before I return distMin and so on... But I couldn't figure it out.
Although I'm sure it can be inferred from the code, I will state the following facts to clarify.
distMtx stores all the intercity distances, and distances are symmetric, meaning if distance from city A to city B is 3, then the distance from city B to city A is also 3. Also, if two cities don't have any direct paths, the distance value is -1.
Any help would be very much appreciated! Thanks!