Dijkstra的Java实现 private int dijkstra(List<int[]>[] graph, int src, int k, int dst) { // 从起点src到达节点i的最短路径权重为distTo[i] int[] distTo = new int[graph.length]; // 定义：从起点src到节点i，至少要经过nodeNumTo[i]个节点 int[] nodeNumTo = new int[graph.length]; Arrays.fill(distTo, Integer.MAX_VALUE); Arrays.fill(nodeNumTo, Integer.MAX_VALUE); // base case distTo[src] = 0; nodeNumTo[src] = 0; // 优先队列，costFromSrc较小的排在前面 Queue<State> pq = new PriorityQueue<>((a, b) -> a.costFromSrc - b.costFromSrc); // 从起点src开始进行BFS pq.offer(new State(src, 0, 0)); while (!pq.isEmpty()) { State curState = pq.poll(); int curId = curState.id; int curCostFromSrc = curState.costFromSrc; int curNodeNumFromSrc = curState.nodeNumFromSrc; if (curId == dst) { // 找到最短路径 return curCostFromSrc; } if (curNodeNumFromSrc == k) { // 中转次数耗尽 continue; } // 将curId 的相邻节点装入队列 for (int[] neighbor : graph[curId]) { int nextId = neighbor[0]; int costToNextNode = curCostFromSrc + neighbor[1]; // 中转次数 int nextNodeNumFromSrc = curNodeNumFromSrc + 1; // 更新dp table if (distTo[nextId] > costToNextNode) { distTo[nextId] = costToNextNode; nodeNumTo[nextId] = nextNodeNumFromSrc; } // 剪枝 if (costToNextNode > distTo[nextId] && nextNodeNumFromSrc > nodeNumTo[nextId]) { continue; } pq.offer(new State(nextId, costToNextNode, nextNodeNumFromSrc)); } } return -1; }