Java求解地铁线路问题

在Java中解决地铁线路问题通常涉及到图论算法，比如最短路径或旅行商问题(TSP - Traveling Salesman Problem)。这类问题模拟城市间的地铁站点和路线，常见的目标可能是找到从一个站到另一个站的最优路径，或者计算出访问所有站点的最小总行程。

例如，Dijkstra算法或A*搜索算法常用于寻找两点之间的最短路径；而如果要考虑所有的站点，可以使用贪心算法、动态规划或甚至启发式搜索如模拟退火算法来近似解决TSP。

以下是一个简单的Dijkstra算法示例：

import java.util.*;

public class ShortestPath {
    private final int[][] graph; // 地铁线路图，每个元素表示两个站点之间的距离

    public List<int[]> dijkstra(int start) {
        int n = graph.length;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]); // 优先队列，按距离排序
        boolean[] visited = new boolean[n]; // 标记已访问节点
        pq.offer(new int[]{start, 0}); // 开始节点，距离为0

        while (!pq.isEmpty()) {
            int[] current = pq.poll(); // 取出距离最小的节点
            int node = current[0];
            if (visited[node]) continue;

            visited[node] = true; // 标记当前节点为已访问

            for (int neighbor = 0; neighbor < n; neighbor++) {
                int distance = current[1] + graph[node][neighbor];
                if (!visited[neighbor] && (distance < graph[node][neighbor])) { // 更新邻接点的距离
                    pq.offer(new int[]{neighbor, distance});
                }
            }
        }

        return Arrays.asList(Arrays.copyOfRange(pq.peek(), 0, n)); // 返回从起点到终点的最短路径
    }
}