java校园导航最短路径查询

要实现校园导航最短路径查询，可以使用图论中的最短路径算法。以下是一种基于 Dijkstra 算法的 Java 实现：

import java.util.*;

public class ShortestPath {
    
    private int[][] graph; // 存储校园地图的邻接矩阵
    private int[] dist; // 存储起点到各个顶点的最短距离
    private boolean[] visited; // 存储顶点是否已经被访问过
    private int start; // 起点
    
    public ShortestPath(int[][] graph, int start) {
        this.graph = graph;
        this.start = start;
        dist = new int[graph.length];
        visited = new boolean[graph.length];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
    }
    
    public int[] getDist() {
        // 使用 Dijkstra 算法计算最短路径
        for (int i = 0; i < graph.length; i++) {
            int minDist = Integer.MAX_VALUE;
            int minIndex = -1;
            for (int j = 0; j < graph.length; j++) {
                if (!visited[j] && dist[j] < minDist) {
                    minDist = dist[j];
                    minIndex = j;
                }
            }
            if (minIndex == -1) break;
            visited[minIndex] = true;
            for (int j = 0; j < graph.length; j++) {
                if (!visited[j] && graph[minIndex][j] != 0 && dist[minIndex] + graph[minIndex][j] < dist[j]) {
                    dist[j] = dist[minIndex] + graph[minIndex][j];
                }
            }
        }
        return dist;
    }
    
    public static void main(String[] args) {
        // 假设校园地图有 5 个地点，用邻接矩阵表示为下面的二维数组
        int[][] graph = {
            {0, 2, 0, 0, 5},
            {2, 0, 1, 0, 0},
            {0, 1, 0, 3, 0},
            {0, 0, 3, 0, 1},
            {5, 0, 0, 1, 0}
        };
        // 假设起点为 0，即 A 地点
        ShortestPath shortestPath = new ShortestPath(graph, 0);
        int[] dist = shortestPath.getDist();
        // 打印起点到各个地点的最短距离
        for (int i = 0; i < dist.length; i++) {
            System.out.println("起点到地点 " + i + " 的最短距离为：" + dist[i]);
        }
    }
}

在上面的代码中，我们使用一个二维数组 `graph` 来存储校园地图的邻接矩阵，其中第 i 行第 j 列的值表示顶点 i 和顶点 j 之间有没有边，如果有，则为边的长度，如果没有，则为 0。例如，上面的邻接矩阵表示的校园地图中，A 地点和 B 地点之间有一条长度为 2 的边，A 地点和 E 地点之间有一条长度为 5 的边，B 地点和 C 地点之间有一条长度为 1 的边，等等。

在 `ShortestPath` 类的构造函数中，我们初始化了起点到各个顶点的最短距离 `dist` 数组，将起点到自身的距离设为 0，其他顶点的距离设为正无穷大。同时，我们也初始化了一个 `visited` 数组，用于记录哪些顶点已经被访问过。

在 `getDist` 方法中，我们使用 Dijkstra 算法计算最短路径。具体来说，我们先找到起点到所有未访问过的顶点中距离最短的那个顶点，将其标记为已访问过，并更新起点到它相邻的顶点的最短距离。然后，我们再从未访问过的顶点中找到距离最短的顶点，重复上述操作，直到所有顶点都被访问过为止。

最后，我们在 `main` 方法中创建一个 `ShortestPath` 对象，传入邻接矩阵和起点，然后调用 `getDist` 方法得到起点到各个顶点的最短距离，并打印出来。对于上面的校园地图，输出如下：

起点到地点 0 的最短距离为：0
起点到地点 1 的最短距离为：2
起点到地点 2 的最短距离为：3
起点到地点 3 的最短距离为：5
起点到地点 4 的最短距离为：5

这表明，从 A 地点出发，最短路径分别为 A-B、A-B-C、A-B-C-D、A-E、A-E-D，它们的长度分别为 2、3、5、5、5。