17｜选路算法：Dijkstra是如何解决最短路问题的？

Dijkstra 算法是逐步构建最短路径树，树中的节点的最短距离不依赖于树外节点，这样才可以一个节点加入最短路径树之后，距离不再改变。负权节点的存在会让加入最短路径树的节点的真实最短路径会因为不在树中的节点而改变，整个算法也就无效了。 如果用最小堆作为数据结构选择最短路径，可以让内存循环的复杂度降为lg V，最终的复杂度可以降为(V+E)lg V

有时候在想:负权边的意义是什么? 应用场景在哪里?🤪

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; }