小明想要游览6个景点,以各景点之间的距离建成double类型的二维数组,随机选取出发地点,基于图论理论建立模型,给出游览完每个景点的最短路径并输出经过景点顺序,求理解较为简单的java代码
时间: 2024-03-19 16:45:22 浏览: 64
好的,根据你的要求,我来给你提供一份理解较为简单的Java代码:
```java
import java.util.*;
public class ShortestPath {
private static final int INF = Integer.MAX_VALUE; // 表示两景点之间无法到达的距离
public static void main(String[] args) {
int[][] distances = { // 二维数组表示各景点之间的距离
{0, 5, 2, 6, INF, INF},
{5, 0, 4, INF, INF, 7},
{2, 4, 0, 3, 2, INF},
{6, INF, 3, 0, 5, INF},
{INF, INF, 2, 5, 0, 4},
{INF, 7, INF, INF, 4, 0}
};
int start = new Random().nextInt(distances.length); // 随机选取出发地点
System.out.println("出发地点:" + start);
int[] path = shortestPath(distances, start); // 计算最短路径
System.out.print("最短路径:");
for (int i : path) {
System.out.print(i + " ");
}
System.out.println();
}
private static int[] shortestPath(int[][] distances, int start) {
int n = distances.length;
boolean[] visited = new boolean[n]; // 记录每个景点是否已访问
int[] prev = new int[n]; // 记录到达每个景点的前一个景点
int[] distancesFromStart = new int[n]; // 记录到达每个景点的最短距离
// 初始化
Arrays.fill(visited, false);
Arrays.fill(prev, -1);
Arrays.fill(distancesFromStart, INF);
distancesFromStart[start] = 0;
// 计算最短路径
for (int i = 0; i < n; i++) {
int u = -1;
int minDistance = INF;
// 找到未访问的离出发点最近的景点
for (int j = 0; j < n; j++) {
if (!visited[j] && distancesFromStart[j] < minDistance) {
u = j;
minDistance = distancesFromStart[j];
}
}
if (u == -1) break; // 如果所有景点都已访问过,则结束循环
visited[u] = true;
// 更新与 u 相邻的景点到出发点的距离
for (int v = 0; v < n; v++) {
if (!visited[v] && distances[u][v] != INF && distancesFromStart[u] + distances[u][v] < distancesFromStart[v]) {
distancesFromStart[v] = distancesFromStart[u] + distances[u][v];
prev[v] = u;
}
}
}
// 根据 prev 数组回溯最短路径
List<Integer> path = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (i == start) continue;
int j = i;
while (j != -1) {
path.add(j);
j = prev[j];
}
Collections.reverse(path);
System.out.print("出发地点 -> " + start + " -> ");
for (int k : path) {
System.out.print(k + " -> ");
}
System.out.println("出发地点,距离为:" + distancesFromStart[i]);
path.clear();
}
return prev;
}
}
```
这份代码使用 Dijkstra 算法计算最短路径,其中 `distances` 数组表示各景点之间的距离,`start` 表示随机选取的出发地点。在 `shortestPath` 方法中,我们使用三个数组 `visited`、`prev` 和 `distancesFromStart` 分别记录每个景点是否已访问、到达每个景点的前一个景点、到达每个景点的最短距离。
在计算最短路径时,我们先找到未访问的离出发点最近的景点,然后更新与该景点相邻的未访问的景点到出发点的距离。最后,根据 `prev` 数组回溯最短路径,并输出经过景点顺序和距离。
阅读全文