Dijkstra算法（朴素版堆优化版）
一.写题选哪个版本：
我怎么知道题目是节点少边少、节点少边多、节点多边少、节点多边多呢
这个问题问得非常实际！能问出这个问题，说明你已经完全不满足于“背代码”了。
我直接给你一套肉眼判断法，不用分析复杂度，扫一眼题目就能决定用哪个算法。
1、四种情况的判断标准（直接看输入范围）
题目一定会给出数据范围，这就是你的判断依据：
| 情况 | V（节点数） | E（边数） | 特点 | 算法选择 |
|---|---|---|---|---|
| 节点少边少 | ≤ 500 | ≤ 5000 | 稀疏图 | 堆优化 Dijkstra / 朴素也行 |
| 节点少边多 | ≤ 500 | ≈ V²（完全图） | 稠密图 | 朴素 Dijkstra（O(V²) 最快） |
| 节点多边少 | 10⁴ ~ 10⁵ | 10⁵ ~ 10⁶ | 稀疏图 | 堆优化 Dijkstra（必须） |
| 节点多边多 | 10⁴ ~ 10⁵ | ≈ V²（几乎不可能出现） | 稠密大图 | 基本不会出现（会爆内存） |
2、具体题目对照
| 题目 | V 范围 | E 范围 | 类型 | 推荐算法 |
|---|---|---|---|---|
| 743 网络延迟 | n ≤ 100 | E ≤ 6000 | 节点少边多（稠密） | 朴素 Dijkstra✅ |
| 1334 阈值距离 | n ≤ 100 | E 可能很多 | 节点少边多 | 朴素 Dijkstra✅ |
| 1631 最小体力 | m×n ≤ 10⁴ | ≈ 4V（网格图） | 节点多边少 | 堆优化 Dijkstra✅ |
| 1584 连接点 | n ≤ 1000 | 完全图（V²/2） | 节点中等边极多 | 朴素 Prim（稠密） |
3、更简单的判断口诀（面试够用）
V 小（≤ 500）→ 无脑朴素
V 大（> 1000）→ 无脑堆优化
为什么？
V 小的时候，O(V²) 最多 25 万，堆优化的常数反而吃亏
V 大的时候，O(V²) 会爆炸（1 亿+），必须用 O(E log V)
二.dijkstra朴素版
1.基础代码：
package com.Dijkstra; import java.util.Arrays; public class Dijkstra { public static void main(String[] args) { int n=5; int INF=Integer.MAX_VALUE/2; int[][] graph={ {0, 2, INF, 6, INF}, {2, 0, 3, 8, 5}, {INF, 3, 0, INF, 7}, {6, 8, INF, 0, 9}, {INF, 5, 7, 9, 0} }; int start=0; int[] dist=dijkstra(n,graph,start); System.out.println("从0节点到其他所有节点的距离："); for (int i = 0; i < n; i++) { if(i==start) continue; System.out.println("0->"+i+": "+dist[i]); } } public static int[] dijkstra(int n,int[][] graph,int start){ int[] dist=new int[n]; boolean[] visited=new boolean[n]; int[] parent=new int[n]; //初始化 Arrays.fill(dist,Integer.MAX_VALUE); Arrays.fill(parent,-1); dist[start]=0; for (int i = 0; i < n; i++) { int cur=-1; int min=Integer.MAX_VALUE; //找最小 for (int j = 0; j < n; j++) { if(!visited[j]&&dist[j]<min){ min=dist[j]; cur=j; } } if(cur==-1) break; visited[cur]=true; //更新邻居路径 for (int j = 0; j < n; j++) { if(!visited[j]){ int newDist=dist[cur]+graph[cur][j]; if(newDist<dist[j]){ dist[j]=newDist; parent[j]=cur; } } } } return dist; } }2.思路：
dist[]存的是七点到该节点的最短路径
visited[]是该节点是否激活（是否被访问过），true是激活，false是未激活
parent[]存的是得到该节点的最短路径的上一个节点，也就是父结点，看是谁使它更新的最短路径
先找最小节点并用cur记录，再更新邻居节点的最短路径
细节：
1.注意是有向图还是无向图，如果是无向图再更新邻居节点的时候就要分类讨论谁作为邻居和cur本身
2.newDist的计算是dist[cur]+该两点之间的路径长度，进行newDist和dist[邻居]比较
三.dijkstra堆优化版
1.基础代码
package com.Dijkstra; import java.util.*; public class DijkstraHeap { /** * Dijkstra 堆优化版（求从 start 到所有点的最短距离） * @param n 节点个数（编号 0 ~ n-1） * @param graph 邻接表，graph[u] = List<int[]{v, w}> 表示 u->v 边权 w * @param start 起点 * @return dist 数组，dist[i] 表示 start 到 i 的最短距离 */ public static int[] dijkstra(int n, List<int[]>[] graph, int start) { // 1. 距离数组，初始化为无穷大 int[] dist = new int[n]; Arrays.fill(dist, Integer.MAX_VALUE); dist[start] = 0; // 2. 优先队列（小顶堆），存 [节点, 当前最短距离] PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]); pq.offer(new int[]{start, 0}); // 3. 主循环 while (!pq.isEmpty()) { int[] cur = pq.poll(); int u = cur[0]; int d = cur[1]; // 如果队列里的距离比已经记录的远，跳过（重要优化） if (d > dist[u]) continue; // 遍历所有邻居 for (int[] edge : graph[u]) { int v = edge[0]; int w = edge[1]; int newDist = dist[u] + w; if (newDist < dist[v]) { dist[v] = newDist; pq.offer(new int[]{v, newDist}); } } } return dist; } }2.思路
利用堆每次poll最小的节点，然后更新邻居节点的dist，在更新的同时要进行pq.offer( );
解释：if (d > dist[u]) continue;
在操作的过程中会出现更新的情况，假如说节点2的现在的最短路径是dist[2]=5,然后在往下继续遍历的过程中节点2的最短路径现在是d=10,pq = {2[10], 2[8]}，然后根据pq的性质是升序排列的pq就会先弹出的是 2[8]，再弹出 2[10]，如果不加if (d > dist[u]) continue;让 2[10]直接退出，会造成它会向下错误的改变邻居节点的dist
举例：
修改一点图结构，加一个节点 3：
text
0 → 1 (5) 0 → 2 (10) 1 → 2 (3) 2 → 3 (1)
目标还是 0 → 2（顺便看一下 3 会不会被错误更新）。
正确最短路径：
0 → 1 → 2 → 3
5 + 3 + 1 =9
如果没有if (d > dist[u]) continue
初始状态：
text
dist = [0, ∞, ∞, ∞] pq = [0[0]]
第 1 步：弹出 [0,0]
更新 [1,5]、[2,10]
pq = [1[5], 2[10]]
第 2 步：弹出 [1,5]
更新 [2,8]
pq = [2[8], 2[10]]
第 3 步：弹出 [2,8] ✅
更新 [3,9]
pq = [2[10], 3[9]]
第 4 步：弹出 [2,10]❌ 旧数据
没有
continue的话，会执行这一行：newDist = dist[2] + 1 = 10 + 1 = 11比较
11 < dist[3] (9)❌ 不成立，不会更新
四.刷题
两种方法都可以写：
743. 网络延迟时间
1334. 阈值距离内邻居最少的城市
只能用堆优化版：
1631. 最小体力消耗路径（因为该题是 节点多n*n 10^4 边少）
1514. 概率最大的路径（节点多边少）
复习：01dx课程🙂