2023年7月30日发(作者：)

[leetcode]——四种图的最短路径算法⽬录前⾔以为例。该题是要求⼀个有向图中，从某⼀个点开始，到达所有点的最短路径中的最⼤值。图的最短路算法单源最短路不带负权边:Dijkstra思路:确定⼀个出发点，每⼀个时间步，从所有没有到达过的点中，选择⼀个与出发点距离最短的点（如果不存在，则结束），此距离就是出发点到该点的最短距离。把该点设置为已到达，并将该点作为中间点，更新出发点和剩余未到达点的最短距离。注意两点: 1. 为什么"此距离就是出发点到该点的最短距离"，因为如果存在另⼀条路径，使得出发点到该点距离更短，那⾸先需要满⾜的是:出发点到下⼀个点的距离⼀定是⼩于这个最短距离的，那如果是⼩于的，当前时间步为什么不选择这个点呢？ 2. 如果存在负边，Dijkstra不成⽴。代码(100%, 21.91%):class Solution { int[][] graph; int MAX_VALUE = _VALUE / 2; public int networkDelayTime(int[][] times, int n, int k) { graph = new int[n+1][n+1]; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ graph[i][j] = i == j ? 0 : MAX_VALUE; } } for(int[] edge:times){ int u = edge[0]; int v = edge[1]; int w = edge[2]; graph[u][v] = w; } int[] dis_lst = graph[k]; //这样graph本⾝也会被改变，不过不影响 boolean[] vis = new boolean[n+1]; vis[k] = true; for(int i = 1; i < n; i++){ int min_dis = MAX_VALUE; int v = -1; for(int j = 1; j <= n; j++){ if(!vis[j] && dis_lst[j] < min_dis){ min_dis = dis_lst[j]; v = j; } } if(v == -1){ break; } vis[v] = true; for(int j = 1; j <= n; j++){ if(!vis[j]){ dis_lst[j] = (dis_lst[j], dis_lst[v] + graph[v][j]); } } } int ans = 0; for(int dis:dis_lst){ ans = (ans, dis); } return ans == MAX_VALUE ? -1 : ans; }}算法复杂度:时间:O(N^2+E)空间:O(N^2)带负权边:Bellman-FordSPFABellman-Ford:思路：最多需要循环n-1次，每⼀次遍历所有边，进⾏更新。第i次的更新，得到的是：出发点最多经过i条边，到达各点的最短路径。两种优化⽅式:某⼀次没有发⽣更新，直接停每⼀次只选择特定的边进⾏更新，即：如果上⼀次的⼀条边u->v更新成功，则这⼀次v的出边是需要考虑⽤来进⾏更新的。(SPFA)代码:（Bellman-Ford）(89.76%，91.12%)class Solution { int MAX_VALUE = _VALUE / 2; public int networkDelayTime(int[][] times, int n, int k) { /* 不需要建图，直接使⽤边即可 graph = new int[n+1][n+1]; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ graph[i][j] = i == j ? 0 : MAX_VALUE; } } for(int[] edge:times){ int u = edge[0]; int v = edge[1]; int w = edge[2]; graph[u][v] = w; } */ int[] dis_lst = new int[n+1]; (dis_lst, MAX_VALUE); dis_lst[k] = 0; dis_lst[0] = 0; //否则出错 for(int x = 0; x < n; x ++){ int flag = 0; for(int[] edge:times){ int u = edge[0]; int v = edge[1]; int w = edge[2]; if(dis_lst[v] > dis_lst[u] + w){ dis_lst[v] = dis_lst[u] + w; flag = 1; } } if(flag == 0){ // 优化1：没有更新，直接结束 break; } } int ans = 0; for(int dis:dis_lst){ ans = (ans, dis); } return ans == MAX_VALUE? -1 : ans; }}算法复杂度:时间:O(N*E)空间:O(E)SPFA：思路，在bellman-ford的基础上，每⼀次只考虑特定的边，即优化2。使⽤队列来维护。代码（89.76%，52.70%）:class Solution { int[][] graph; int MAX_VALUE = _VALUE / 2; public int networkDelayTime(int[][] times, int n, int k) { graph = new int[n+1][n+1]; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ graph[i][j] = i == j ? 0 : MAX_VALUE; } } for(int[] edge:times){ int u = edge[0]; int v = edge[1]; int w = edge[2]; graph[u][v] = w; } int[] dis_lst = new int[n+1]; (dis_lst, MAX_VALUE); dis_lst[0] = dis_lst[k] = 0; Queue q= new LinkedList(); (k); while(!y()){ int now = (); //遍历该点出发的所有边，进⾏更新 for(int i = 1; i <= n; i ++){ if(dis_lst[i] > dis_lst[now] + graph[now][i]){ dis_lst[i] = dis_lst[now] + graph[now][i]; (i); } } } int ans = 0; for(int dis:dis_lst){ ans = (ans, dis); } return ans == MAX_VALUE? -1 : ans; }}算法复杂度:不会多源最短路:Floyd思路：对于G中任意两个顶点v、w，遍历除这两点以外的所有其它点，假设以该点为中间点，更新v和w之间的最短距离。代码:（58%， 15%）/*返回出发点，到达所有点的最短路径中的最⼤值*/class Solution { int[][] graph; int MAX_VALUE = _VALUE / 2; //防⽌下⾯graph[i][x] + graph[x][j]的时候，数值超过上限，反⽽变⼩ public int networkDelayTime(int[][] times, int n, int k) { //建图 graph = new int[n+1][n+1]; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ graph[i][j] = i == j ? 0 : MAX_VALUE; } } for(int[] edge:times){ int u = edge[0]; int v = edge[1]; int w = edge[2]; graph[u][v] = w; } //floyd for(int x = 1; x <= n; x++){ for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ graph[i][j] = (graph[i][j], graph[i][x] + graph[x][j]); } } } //最⼤的最短路径

int ans = 0; for(int dis:graph[k]){ //这⾥要注意graph[k][0]这个位置的值，千万不要初始化为MAX_VALUE ans = (ans, dis); } return ans == MAX_VALUE ? -1 : ans; }}算法复杂度:时间:O(N^3)空间:O(N^2 + E)参考