一.写题选哪个版本我怎么知道题目是节点少边少、节点少边多、节点多边少、节点多边多呢这个问题问得非常实际能问出这个问题说明你已经完全不满足于“背代码”了。我直接给你一套肉眼判断法不用分析复杂度扫一眼题目就能决定用哪个算法。1、四种情况的判断标准直接看输入范围题目一定会给出数据范围这就是你的判断依据情况V节点数E边数特点算法选择节点少边少≤ 500≤ 5000稀疏图堆优化 Dijkstra / 朴素也行节点少边多≤ 500≈ V²完全图稠密图朴素 DijkstraO(V²) 最快节点多边少10⁴ ~ 10⁵10⁵ ~ 10⁶稀疏图堆优化 Dijkstra必须节点多边多10⁴ ~ 10⁵≈ V²几乎不可能出现稠密大图基本不会出现会爆内存2、具体题目对照题目V 范围E 范围类型推荐算法743 网络延迟n ≤ 100E ≤ 6000节点少边多稠密朴素 Dijkstra✅1334 阈值距离n ≤ 100E 可能很多节点少边多朴素 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 n5; int INFInteger.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 start0; int[] distdijkstra(n,graph,start); System.out.println(从0节点到其他所有节点的距离); for (int i 0; i n; i) { if(istart) continue; System.out.println(0-i: dist[i]); } } public static int[] dijkstra(int n,int[][] graph,int start){ int[] distnew int[n]; boolean[] visitednew boolean[n]; int[] parentnew 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 minInteger.MAX_VALUE; //找最小 for (int j 0; j n; j) { if(!visited[j]dist[j]min){ mindist[j]; curj; } } if(cur-1) break; visited[cur]true; //更新邻居路径 for (int j 0; j n; j) { if(!visited[j]){ int newDistdist[cur]graph[cur][j]; if(newDistdist[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] Listint[]{v, w} 表示 u-v 边权 w * param start 起点 * return dist 数组dist[i] 表示 start 到 i 的最短距离 */ public static int[] dijkstra(int n, Listint[][] graph, int start) { // 1. 距离数组初始化为无穷大 int[] dist new int[n]; Arrays.fill(dist, Integer.MAX_VALUE); dist[start] 0; // 2. 优先队列小顶堆存 [节点, 当前最短距离] PriorityQueueint[] 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的最短路径现在是d10,pq {2[10], 2[8]}然后根据pq的性质是升序排列的pq就会先弹出的是 2[8]再弹出 2[10]如果不加if (d dist[u]) continue;让 2[10]直接退出会造成它会向下错误的改变邻居节点的dist举例修改一点图结构加一个节点 3text0 → 1 (5) 0 → 2 (10) 1 → 2 (3) 2 → 3 (1)目标还是 0 → 2顺便看一下 3 会不会被错误更新。正确最短路径0 → 1 → 2 → 35 3 1 9如果没有if (d dist[u]) continue初始状态textdist [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课程
`)
