You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
53 lines
1.4 KiB
Java
53 lines
1.4 KiB
Java
import java.util.*;
|
|
|
|
public class ShortestHamiltonianCycle {
|
|
|
|
public static int getShortestHamiltonianCycle(int[][] dist) {
|
|
int n = dist.length;
|
|
int[][] dp = new int[1 << n][n];
|
|
for (int[] d : dp)
|
|
Arrays.fill(d, Integer.MAX_VALUE / 2);
|
|
dp[1][0] = 0;
|
|
for (int mask = 1; mask < 1 << n; mask += 2) {
|
|
for (int i = 1; i < n; i++) {
|
|
if ((mask & 1 << i) != 0) {
|
|
for (int j = 0; j < n; j++) {
|
|
if ((mask & 1 << j) != 0) {
|
|
dp[mask][i] = Math.min(dp[mask][i], dp[mask ^ (1 << i)][j] + dist[j][i]);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
int res = Integer.MAX_VALUE;
|
|
for (int i = 1; i < n; i++) {
|
|
res = Math.min(res, dp[(1 << n) - 1][i] + dist[i][0]);
|
|
}
|
|
|
|
// reconstruct path
|
|
int cur = (1 << n) - 1;
|
|
int[] order = new int[n];
|
|
int last = 0;
|
|
for (int i = n - 1; i >= 1; i--) {
|
|
int bj = -1;
|
|
for (int j = 1; j < n; j++) {
|
|
if ((cur & 1 << j) != 0 && (bj == -1 || dp[cur][bj] + dist[bj][last] > dp[cur][j] + dist[j][last])) {
|
|
bj = j;
|
|
}
|
|
}
|
|
order[i] = bj;
|
|
cur ^= 1 << bj;
|
|
last = bj;
|
|
}
|
|
System.out.println(Arrays.toString(order));
|
|
return res;
|
|
}
|
|
|
|
// Usage example
|
|
public static void main(String[] args) {
|
|
int[][] dist = { { 0, 1, 10, 1, 10 }, { 1, 0, 10, 10, 1 }, { 10, 10, 0, 1, 1 }, { 1, 10, 1, 0, 10 },
|
|
{ 10, 1, 1, 10, 0 } };
|
|
System.out.println(5 == getShortestHamiltonianCycle(dist));
|
|
}
|
|
}
|