经销商问题6个结点最后回到起点,求路程最短,用遍历所有路径并比较的方法求结果,给出代码用java,数据用hashmap存储
时间: 2024-03-24 11:40:35 浏览: 14
好的,以下是用Java实现的代码:
```java
import java.util.HashMap;
import java.util.Map;
public class ShortestPath {
private int[][] graph; // 存储图的邻接矩阵
private int[] path; // 存储路径
private int minDist = Integer.MAX_VALUE; // 记录最短路径长度
public ShortestPath(Map<Integer, int[]> data) {
int n = data.size(); // 结点个数
graph = new int[n][n];
// 初始化邻接矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
graph[i][j] = Integer.MAX_VALUE;
}
}
// 构建邻接矩阵
for (Map.Entry<Integer, int[]> entry : data.entrySet()) {
int node = entry.getKey();
int[] neighbors = entry.getValue();
for (int neighbor : neighbors) {
graph[node][neighbor] = 1;
}
}
path = new int[n];
path[0] = 0; // 起点为0
dfs(1, 0, n); // 从第二个结点开始遍历
}
// 深度优先遍历所有路径
private void dfs(int depth, int dist, int n) {
if (depth == n) { // 所有结点都已经遍历完
if (graph[path[n - 1]][0] != Integer.MAX_VALUE) { // 如果最后一个结点可以回到起点
minDist = Math.min(minDist, dist + graph[path[n - 1]][0]); // 更新最短路径长度
}
return;
}
for (int i = 1; i < n; i++) {
if (!contains(path, i)) { // 如果结点i没有被遍历过
if (graph[path[depth - 1]][i] != Integer.MAX_VALUE) { // 如果当前结点可以到达i
path[depth] = i; // 记录路径
dfs(depth + 1, dist + graph[path[depth - 1]][i], n); // 继续遍历下一个结点
}
}
}
}
// 判断数组中是否包含某个元素
private boolean contains(int[] array, int target) {
for (int element : array) {
if (element == target) {
return true;
}
}
return false;
}
public int getMinDist() {
return minDist;
}
public static void main(String[] args) {
Map<Integer, int[]> data = new HashMap<>();
data.put(0, new int[]{1, 2, 3, 4, 5});
data.put(1, new int[]{0, 2, 3, 4, 5});
data.put(2, new int[]{0, 1, 3, 4, 5});
data.put(3, new int[]{0, 1, 2, 4, 5});
data.put(4, new int[]{0, 1, 2, 3, 5});
data.put(5, new int[]{0, 1, 2, 3, 4});
ShortestPath sp = new ShortestPath(data);
System.out.println(sp.getMinDist()); // 输出最短路径长度
}
}
```
上面的代码中,我们利用一个HashMap存储了结点的邻居结点,然后根据这个HashMap构建了邻接矩阵。接着,我们从起点0开始遍历所有路径,用一个数组path记录路径,用一个变量dist记录路径长度。当遍历到最后一个结点时,如果最后一个结点可以回到起点,我们就更新最短路径长度。最后输出最短路径长度即可。