目录

floyd

-dijkstra

floyd

floyd:用来求所有顶点之间的最短路径问题,求最短路径具体节点顺序，求各点之间最短路径长度

理解floyd：

1. 二维矩阵图，就是不断通过测试新的节点k，看看k节点能不能作为中间节点优化各点之间的最短距离
2. 用动态规划来理解，floyd就是从f[0][i][j]去推求出f[k][i][j],（表示i与j之间允许通过编号为1 ...k的节点的最短路径)

   1. dp[k][i][j] = Min(f[k-1][i][j],f[k-1][i][k]+f[k-1][k][j])

   2. a[i][j] = Math.min(a[i][j], a[i][k] + a[k][j]);

Floyd-Warshall算法的时间复杂度为O(N^3)，空间复杂度为O(N^2)。

图最短路径算法之弗洛伊德算法（Floyd） | Echo Blog

 核心代码

private void floyd() { for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { a[i][j] = Math.min(a[i][j], a[i][k] + a[k][j]); } } } // 打印 for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { System.out.println(i + " " + j + ":" + a[i][j]); } } }

如何记录最短路径呢？

利用path

如果利用k顶点，A矩阵更新了，则在path[i][j]=k

-dijkstra

 dijkstra的目标：从节点start 出发到其他所有节点的最短路径

王道：

1.在堆里面加入的是{id,temp_dis},因为这个temp_dis如果不是最小的，反正会根据disjkra的算法执行下去，会出现同一个id但是dis是真正最短距离的节点,然后真正最短距离的{id,dis}后进来也会先出去。利用vis，就把之前的{id,temp_dis}给忽略了

模板1----力扣

class Solution {int N = 110, M = 6010;// 邻接表int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M];// dist[x] = y 代表从「源点/起点」到 x 的最短距离为 yint[] dist = new int[N];// 记录哪些点已经被更新过boolean[] vis = new boolean[N];int n, k, idx;int INF = 0x3f3f3f3f;void add(int a, int b, int c) {e[idx] = b;ne[idx] = he[a];he[a] = idx;w[idx] = c;idx++;}public int networkDelayTime(int[][] ts, int _n, int _k) {n = _n; k = _k;// 初始化链表头Arrays.fill(he, -1);// 存图for (int[] t : ts) {int u = t[0], v = t[1], c = t[2];add(u, v, c);}// 最短路dijkstra();// 遍历答案int ans = 0;for (int i = 1; i <= n; i++) {ans = Math.max(ans, dist[i]);}return ans > INF / 2 ? -1 : ans;}void dijkstra() {// 起始先将所有的点标记为「未更新」和「距离为正无穷」Arrays.fill(vis, false);Arrays.fill(dist, INF);// 只有起点最短距离为 0dist[k] = 0;// 使用「优先队列」存储所有可用于更新的点// 以 (点编号, 到起点的距离) 进行存储，优先弹出「最短距离」较小的点PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[1]-b[1]);q.add(new int[]{k, 0});while (!q.isEmpty()) {// 每次从「优先队列」中弹出int[] poll = q.poll();int id = poll[0], step = poll[1];// 如果弹出的点被标记「已更新」，则跳过if (vis[id]) continue;// 标记该点「已更新」，并使用该点更新其他点的「最短距离」vis[id] = true;for (int i = he[id]; i != -1; i = ne[i]) {int j = e[i];if (dist[j] > dist[id] + w[i]) {dist[j] = dist[id] + w[i];q.add(new int[]{j, dist[j]});}}}}
}作者：宫水三叶
链接：https://leetcode.cn/problems/network-delay-time/solutions/910056/gong-shui-san-xie-yi-ti-wu-jie-wu-chong-oghpz/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

模板2

1.用最小堆优化过

2.distTo[i]是最终确定的，从起点到i的最短距离

3.用disTo[i]是否<，来代替visite[]

3.State.disFromStart是过程中不断记录的当前到点的路径距离

class State {// 图节点的 idint id;// 从 start 节点到当前节点的距离int distFromStart;State(int id, int distFromStart) {this.id = id;this.distFromStart = distFromStart;}
}// 返回节点 from 到节点 to 之间的边的权重
int weight(int from, int to);// 输入节点 s 返回 s 的相邻节点
List<Integer> adj(int s);// 输入一幅图和一个起点 start，计算 start 到其他节点的最短距离
int[] dijkstra(int start, List<Integer>[] graph) {// 图中节点的个数int V = graph.length;// 记录最短路径的权重，你可以理解为 dp table// 定义：distTo[i] 的值就是节点 start 到达节点 i 的最短路径权重int[] distTo = new int[V];// 求最小值，所以 dp table 初始化为正无穷Arrays.fill(distTo, Integer.MAX_VALUE);// base case，start 到 start 的最短距离就是 0distTo[start] = 0;// 优先级队列，distFromStart 较小的排在前面Queue<State> pq = new PriorityQueue<>((a, b) -> {return a.distFromStart - b.distFromStart;});// 从起点 start 开始进行 BFSpq.offer(new State(start, 0));while (!pq.isEmpty()) {State curState = pq.poll();int curNodeID = curState.id;int curDistFromStart = curState.distFromStart;if (curDistFromStart > distTo[curNodeID]) {// 已经有一条更短的路径到达 curNode 节点了continue;}// 将 curNode 的相邻节点装入队列for (int nextNodeID : adj(curNodeID)) {// 看看从 curNode 达到 nextNode 的距离是否会更短int distToNextNode = distTo[curNodeID] + weight(curNodeID, nextNodeID);if (distTo[nextNodeID] > distToNextNode) {// 更新 dp tabledistTo[nextNodeID] = distToNextNode;// 将这个节点以及距离放入队列pq.offer(new State(nextNodeID, distToNextNode));}}}return distTo;
}