by Sergey Yakimov
package tsp;
package tsp;
class Tsp {
int[] tsp(int[][] graph) {
int[] path = new int[graph.length];
int[] p = new int[graph.length + 1];
for (int i = 0; i < path.length; i++) path[i] = p[i] = i;
p[graph.length] = graph.length;
int[] costs = new int[graph.length - 1];
int cost = 0;
for (int i = 0; i < costs.length; i++) cost += costs[i] = graph[path[i]][path[i + 1]];
int[] bestPath = path.clone();
int bestCost = cost;
int i = 1;
while (i < graph.length) {
int j = i % 2 * --p[i];
int tmp = path[j];
path[j] = path[i];
path[i] = tmp;
int[] rowI = graph[path[i]];
int[] rowJ = graph[path[j]];
if (i > 0) cost -= costs[i - 1] - (costs[i - 1] = rowI[path[i - 1]]);
if (j > 0) cost -= costs[j - 1] - (costs[j - 1] = rowJ[path[j - 1]]);
if (i < costs.length - 1) cost -= costs[i] - (costs[i] = rowI[path[i + 1]]);
if (j < costs.length - 1) cost -= costs[j] - (costs[j] = rowJ[path[j + 1]]);
i = 1;
while (p[i] == 0) p[i] = i++;
if (cost < bestCost) {
bestPath = path.clone();
bestCost = cost;
}
}
return bestPath;
}
}