用java语言实现地铁最短距离问题

由于地铁的路线是一张图，我们可以使用图论算法来解决地铁最短距离问题。常用的图论算法有Dijkstra算法和Floyd算法。

以下是使用Dijkstra算法实现的Java代码：

import java.util.*;

public class Subway {
    private final int INF = Integer.MAX_VALUE;  // 无穷大表示两站之间没有直接的地铁路线
    private int[][] map;  // 地铁路线图
    private int[] dist;  // 存储每个站点到起点的最短距离
    private boolean[] visited;  // 标记每个站点是否已经访问过
    private int start;  // 起点
    private int end;  // 终点

    public Subway(int[][] map) {
        this.map = map;
        dist = new int[map.length];
        visited = new boolean[map.length];
        Arrays.fill(dist, INF);
    }

    // Dijkstra算法求解最短路径
    public int shortestPath(int start, int end) {
        this.start = start;
        this.end = end;
        dist[start] = 0;
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));
        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int cur = node.idx;
            if (visited[cur]) continue;
            visited[cur] = true;
            for (int i = 0; i < map[cur].length; i++) {
                if (map[cur][i] != INF && !visited[i]) {
                    int newDist = dist[cur] + map[cur][i];
                    if (newDist < dist[i]) {
                        dist[i] = newDist;
                        pq.offer(new Node(i, newDist));
                    }
                }
            }
        }
        return dist[end];
    }

    static class Node implements Comparable<Node> {
        int idx;
        int dist;

        public Node(int idx, int dist) {
            this.idx = idx;
            this.dist = dist;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(dist, o.dist);
        }
    }
}

使用示例：

public class Main {
    public static void main(String[] args) {
        int[][] map = {
            {0, 3, 6, INF, INF, INF},
            {3, 0, 2, 5, INF, INF},
            {6, 2, 0, 4, 6, INF},
            {INF, 5, 4, 0, 2, 3},
            {INF, INF, 6, 2, 0, 5},
            {INF, INF, INF, 3, 5, 0}
        };
        Subway subway = new Subway(map);
        int shortestPath = subway.shortestPath(0, 5);
        System.out.println(shortestPath);  // 输出4，表示从第1号站点到第6号站点最短距离为4
    }
}

上述代码中，我们将地铁路线图表示为邻接矩阵，其中INF表示两站之间没有直接的地铁路线。使用Dijkstra算法求解最短路径时，我们将起点到每个站点的最短距离存储在dist数组中，visited数组用于标记每个站点是否已经访问过，pq是一个优先队列，用于存储当前可到达的所有站点以及它们到起点的距离。在遍历完所有可到达的站点后，dist[end]就是起点到终点的最短距离。