设有n个城市和距离矩阵D=[dij],其中dij表示城市i到城市j的距离,i,j=1,2 … n,则问题是要找出遍访每个城市恰好一次的一条回路并使其路径长度为最短。用java写出代码
时间: 2023-03-13 15:52:11 浏览: 86
用java写出来的代码应该是这样的:
// 导入需要的包
import java.util.Math;
// 定义一个函数,用来计算最短路径
public static int minDistance(int[][] D, int n) {
// 初始化距离矩阵
int[][] dist = new int[n][n];
// 初始化距离矩阵的值
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = D[i][j];
}
}
// 计算最短路径
int minDist = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j) {
for (int k = 0; k < n; k++) {
if (k != i && k != j) {
int tmpDist = dist[i][j] + dist[j][k] + dist[k][i];
if (tmpDist < minDist) {
minDist = tmpDist;
}
}
}
}
}
}
return minDist;
}