Dijkstra算法的学习

Dijkstra算法的学习

学习了前辈 name_s_Jimmy 的文章 算法学习（10）：LeetCode刷题之Dijkstra最短路径算法_leetcode dijkstra-CSDN博客

1. 介绍

Dijkstra最短路径算法，获取有向图上所有点到当前点的最小代价，需要使用邻接表

2. 模板

	/** @description 最短路径算法* @param: edges 邻接表(int[0]是索引，int[1]是权值)* @param: start 起始点* @returns int* @author yamu* @date 2025/4/28 15:43*/public int[] dijkstra(List<List<int[]>> edges, int start) {int[] res = new int[edges.size()];//最小距离数组Arrays.fill(res, Integer.MAX_VALUE);//不可达PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> o1.minVal - o2.minVal);//记录更小距离的点pq.add(new Node(start, 0));//起始点while (!pq.isEmpty()) {Node curNode = pq.poll();int curId = curNode.curId, curDis = curNode.minVal;for (int[] j : edges.get(curId)) {int nextId = j[0], nextDis = j[1] + curDis;if (nextDis < res[nextId]) {pq.add(new Node(nextId, nextDis));res[nextId] = nextDis;}}}return res;}

3. 例题

1. 743. 网络延迟时间 - 力扣（LeetCode）