DeepSeek LeetCode 2642. 设计可以求最短路径的图类 Java实现

下面是 LeetCode 2642「设计可以求最短路径的图类」的 Java 实现。题目理解设计一个 Graph 类支持1. 初始化Graph(int n, int[][] edges) - n 个节点0 到 n-1edges 为有向边 (from, to, cost)2. 添加边addEdge(int[] edge) - 添加一条新边3. 求最短路径shortestPath(int node1, int node2) - 返回 node1 到 node2 的最短路径长度不存在返回 -1核心思路使用** Dijkstra 算法**由于需要动态添加边每次查询时运行 Dijkstra 即可n ≤ 100edges ≤ 100查询次数 ≤ 100复杂度可接受。完整实现代码ACjavaimport java.util.*;class Graph {private int n;private Listint[][] graph;public Graph(int n, int[][] edges) {this.n n;graph new ArrayList[n];for (int i 0; i n; i) {graph[i] new ArrayList();}for (int[] edge : edges) {addEdge(edge);}}public void addEdge(int[] edge) {int from edge[0];int to edge[1];int cost edge[2];graph[from].add(new int[]{to, cost});}public int shortestPath(int node1, int node2) {// 距离数组初始化为无穷大int[] dist new int[n];Arrays.fill(dist, Integer.MAX_VALUE);dist[node1] 0;// 优先队列存储 [距离, 节点]PriorityQueueint[] pq new PriorityQueue(Comparator.comparingInt(a - a[0]));pq.offer(new int[]{0, node1});while (!pq.isEmpty()) {int[] curr pq.poll();int currDist curr[0];int currNode curr[1];// 如果当前距离大于记录的距离跳过if (currDist dist[currNode]) {continue;}// 到达目标节点可以提前返回因为 Dijkstra 第一次弹出就是最短if (currNode node2) {return currDist;}// 遍历邻接边for (int[] neighbor : graph[currNode]) {int nextNode neighbor[0];int weight neighbor[1];int newDist currDist weight;if (newDist dist[nextNode]) {dist[nextNode] newDist;pq.offer(new int[]{newDist, nextNode});}}}return dist[node2] Integer.MAX_VALUE ? -1 : dist[node2];}}优化版本使用邻接矩阵 Floyd 预计算如果查询次数很多可以使用 Floyd-Warshall 算法在每次添加边后更新全对最短路径。javaclass Graph {private int n;private int[][] dist;public Graph(int n, int[][] edges) {this.n n;// 初始化距离矩阵dist new int[n][n];for (int i 0; i n; i) {Arrays.fill(dist[i], Integer.MAX_VALUE / 2); // 避免溢出dist[i][i] 0;}for (int[] edge : edges) {int from edge[0];int to edge[1];int cost edge[2];dist[from][to] Math.min(dist[from][to], cost);}// Floyd-Warshall 预计算floydWarshall();}private void floydWarshall() {for (int k 0; k n; k) {for (int i 0; i n; i) {for (int j 0; j n; j) {if (dist[i][k] dist[k][j] dist[i][j]) {dist[i][j] dist[i][k] dist[k][j];}}}}}public void addEdge(int[] edge) {int from edge[0];int to edge[1];int cost edge[2];// 如果新边比现有路径更短更新并重新运行 Floydif (cost dist[from][to]) {dist[from][to] cost;// 只更新受影响的路径for (int i 0; i n; i) {for (int j 0; j n; j) {if (dist[i][from] cost dist[to][j] dist[i][j]) {dist[i][j] dist[i][from] cost dist[to][j];}}}}}public int shortestPath(int node1, int node2) {return dist[node1][node2] Integer.MAX_VALUE / 2 ? -1 : dist[node1][node2];}}使用示例javapublic class Main {public static void main(String[] args) {// 初始化4个节点边列表int[][] edges {{0, 1, 1}, {1, 2, 2}, {2, 3, 3}};Graph graph new Graph(4, edges);System.out.println(graph.shortestPath(0, 3)); // 输出: 6 (0-1-2-3)System.out.println(graph.shortestPath(0, 2)); // 输出: 3 (0-1-2)// 添加新边graph.addEdge(new int[]{0, 2, 2});System.out.println(graph.shortestPath(0, 3)); // 输出: 5 (0-2-3)// 不存在路径System.out.println(graph.shortestPath(3, 0)); // 输出: -1}}复杂度分析方案一Dijkstra· 初始化O(E)· addEdgeO(1)· shortestPathO((V E) log V) O((100 100) log 100) ≈ O(200)· 适用场景查询次数少边添加频繁方案二Floyd 预计算· 初始化O(V³) O(100³) 1,000,000· addEdgeO(V²) O(10,000)· shortestPathO(1)· 适用场景查询次数非常多 1000 次关键技巧1. 使用 Integer.MAX_VALUE / 2 避免溢出防止加法运算时溢出2. Dijkstra 早期终止当弹出目标节点时立即返回提高效率3. Floyd 增量更新添加新边时只更新受影响的路径避免全量重算根据题目约束n ≤ 100最多 100 次操作两种方案都可以接受。推荐使用 Dijkstra 方案代码更简洁且不易出错。