区块链技术博客
www.b2bchain.cn

算法-最短路

这篇文章主要介绍了算法-最短路,通过具体代码讲解6056并且分析了算法-最短路的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了算法-最短路。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/?p=6056。具体如下:

算法

算法

发布日期:   2020-03-10
文章字数:   2.4k
阅读时长:   10 分
阅读次数:  

最短路算法

这篇博客主要是记一下最短路板子,板子三天不练就忘(x

回到正题,图的最短路算法有很多,在此记录一下非常常用的三个算法

  • 单源最短路
    • 不带负权边:$Dijkstra$
    • 带负权边:$Bellman-Ford$、$SPFA$
  • 多源最短路
    • $Floyd$

假设图中顶点V个,边E条,有如下结论:

  • $Dijkstra$
    • 本质是贪心+广搜
    • 朴素写法,时间复杂度$O(V^2+E)$,可以认为是$O(V^2)$,这个一般不怎么写,需要松弛,太蠢啦
    • 堆优化(小堆),时间复杂度$O(VlogV+E)$
    • $Dijkstra$ 算法更适合稠密图(边多的图)
    • 无论图有没有环,$Dijkstra$ 算法都是可以用的,它只是不能处理负权边,因为它本质上是贪心策略,每个点选择之后就不再更新,如果碰到了负边的存在就会破坏这个贪心的策略就无法处理了
    • 一般堆优化+邻接矩阵用起来贼爽
  • $SPFA$
    • 它是 $Bellman-Ford$ 的优化,$ Bellman-Ford$的时间复杂度为 $O(VE)$,效率太低了,SPFA是 $Bellman-Ford$ 的队列优化,但是算法时间效率不稳定,时间复杂度为$O(E)$,最好情况下,每个节点只入队一次,就是 $BFS$,最坏情况下,每一个节点都要入队 $V-1$ 次,这时候就退化成$Bellman-Ford$ 了
    • $SPFA$时间复杂度某种情况下略高于 $Dijkstra$, 适合稀疏图
    • $SPFA$ 是可以用于带有负权图的,在 $SPFA$ 中每一个点松弛过后说明这个点距离更近了,所以有可能通过这个点会再次优化其他点,所以它的策略是将 $vis$ 位置为 $false$,把这个点入队再判断一次!这就和 $Dijkstra$ 的贪心策略不同了!
    • $SPFA$ 还有个用处是可以判断图是否存在负环,我们只要用一个 $cnt[x]$ 数组来存放经过这个点的次数,上面提到过,最坏情况下每个节点入队 $V-1$次,如果 $cnt[x]$ 为 $V$ 的个数,那就说明存在负环了。
  • $Floyd$
    • 本质是动态规划,能解决任意两点间的最短路径,时间复杂度 $O(V^3)$
    • 看了 $Aoxiang Cui$ 大佬的一个回复,$ Floyd$它是可以判断有没有负权边环的,走N-1步,如果再走一步,更短了,那么就说明有环。另外 $Floyd$ 是不能处理带有负权的最短路的,因为本质是一个动态规划算法,有了负边,最优子结构的性质就不满足了。由此可见,它能够判断是否存在负环,但是不能够处理带有负权的额最短路
    • $Floyd$ 有个神奇的特性,这个是其他算法没有的,$ Floyd$第 $k$ 轮算的结果,是每个源点到每个汇点经过前 $k$ 个点的最短路,这一点可以出题。

743. 网络延迟时间

Dijkstra(堆优化)

  • times中的数组 a a[0]代表源,a[1]代表目标,a[2]代表权值,单向的

  • 一般堆优化的都用邻接表, map< Integer,List< int[]>>来存放源到目的节点及权值,而朴素dijkstra直接用数组就可以了

  • dijkstra 需要 dis数组和vis数组,都开N+1,dis的初始化要当心,具体是初始化为-1还是INF看情况,其次不要忘记初始化之后再重置dis[源]和dis{0}为0

    public int networkDelayTime(int[][] times, int N, int K) {         Map<Integer, List<int[]>> map = new HashMap<>();         // 初始化邻接表         for (int[] t : times) {             map.computeIfAbsent(t[0], k -> new ArrayList<>()).add(new int[]{t[1], t[2]});         }          // 初始化dis数组和vis数组         int[] dis = new int[N + 1];         Arrays.fill(dis, 0x3f3f3f3f);         boolean[] vis = new boolean[N + 1];          // 起点的dis为0,但是别忘记0也要搞一下,因为它是不参与的,我计算结果的时候直接用了stream,所以这个0也就要初始化下了         dis[K] = 0;         dis[0] = 0;          // new一个小堆出来,按照dis升序排,一定要让它从小到大排,省去了松弛工作         PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> dis[o1] - dis[o2]);         // 把起点放进去         queue.offer(K);          while (!queue.isEmpty()) {             // 当队列不空,拿出一个源出来             Integer poll = queue.poll();                  if(vis[poll]) continue;             // 把它标记为访问过             vis[poll] = true;             // 遍历它的邻居们,当然可能没邻居,这里用getOrDefault处理就很方便             List<int[]> list = map.getOrDefault(poll, Collections.emptyList());             for (int[] arr : list) {                 int next = arr[0];                 // 如果这个邻居访问过了,继续                 if (vis[next]) continue;                 // 更新到这个邻居的最短距离,看看是不是当前poll出来的节点到它更近一点                 dis[next] = Math.min(dis[next], dis[poll] + arr[1]);                 queue.offer(next);             }         }         // 拿到数组中的最大值比较下,返回结果         int res = Arrays.stream(dis).max().getAsInt();         return res == 0x3f3f3f3f ? -1 : res;     }

SPFA

  • SPFA是一种用队列优化的B-F算法,在稀疏图中,采用类似邻接链表储存比较节省空间。
  • 也需要用到dis和vis数组,开N+1,初始化也要看情况

【算法思想】

  1. 初始时,只有把起点放入队列中。
  2. 遍历与起点相连的边,如果可以松弛就更新距离dis[],然后判断如果这个点没有在队列中就入队标记。
  3. 出队队首,取消标记,循环2-3步,直至队为空。
  4. 所有能更新的点都更新完毕,dis[]数组中的距离就是,起点到其他点的最短距离。

ps:这边我犯的一个错误是这样的

Integer poll = queue.poll()if(判断是否是poll的邻居){       if(判断是否需要更新){             // 更新代码     }       if(!vis[next]){       queue.offer(next);       vis[next] = true;     } } ...

这样写是错的,如果图中有环,在不需要更新的情况下,就能重复入队,所以应该改为

Integer poll = queue.poll()if(判断是否是poll的邻居 && 判断是否需要更新){     // 更新代码       // ...       if(!vis[next]){       queue.offer(next);       vis[next] = true;     } } ...

邻接表写法

// SPFA:用邻接表写 public int networkDelayTime(int[][] times, int N, int K) {     Map<Integer, List<int[]>> map = new HashMap<>();     // 构建邻接表     for (int[] arr : times) {         List<int[]> list = map.getOrDefault(arr[0], new ArrayList<>());         list.add(new int[]{arr[1], arr[2]});         map.put(arr[0], list);     }     // 初始化dis数组和vis数组     int[] dis = new int[N + 1];     int INF = 0x3f3f3f3f;     Arrays.fill(dis, INF);       boolean[] vis = new boolean[N + 1];     dis[K] = dis[0] = 0;      Queue<Integer> queue = new LinkedList<>();     queue.offer(K);      while (!queue.isEmpty()) {         // 取出队首节点         Integer poll = queue.poll();         // 可以重复入队         vis[poll] = false;         // 遍历起点的邻居,更新距离         List<int[]> list = map.getOrDefault(poll, Collections.emptyList());         for (int[] arr : list) {             int next = arr[0];             // 如果没更新过,或者需要更新距离()             if (dis[next] == INF || dis[next] > dis[poll] + arr[1]) {                 // 更新距离                 dis[next] = dis[poll] + arr[1];                 // 如果队列中没有,就不需要再次入队了 (那么判断入度可以在这里做文章)                 if (!vis[next]) {                     vis[next] = true;                     queue.offer(next);                 }             }         }             }     int res = Arrays.stream(dis).max().getAsInt();     return res == INF ? -1 : res; }

邻接矩阵写法

public class Solution {      public int networkDelayTime(int[][] times, int N, int K) {         int[][] g = new int[N + 1][N + 1];         // 初始化 graph         for (int i = 1; i <= N; i++) {             for (int j = 1; j <= N; j++) {                 g[i][j] = i == j ? 0 : -1;             }         }         // 单向边         for (int[] t : times) {             g[t[0]][t[1]] = t[2];         }          int INF = 0x3f3f3f3f;         // 初始化 dis、vis         int[] dis = new int[N + 1];         Arrays.fill(dis, INF);         dis[0] = dis[K] = 0;          boolean[] vis = new boolean[N + 1];          Queue<Integer> queue = new LinkedList<>();         queue.offer(K);         vis[K] = true;          while (!queue.isEmpty()) {             Integer poll = queue.poll();             vis[poll] = false;             // 遍历邻居             for (int next = 1; next <= N; next++) {                 // 如果是邻居 且 如果没有更新过,或者是需要更新,才往下走,注意这里是且,并不是判断了邻居就往下走了                 // 下面是错误写法                  /*                 如果是邻居,,一定要在这一步全部写完,如果能更新才能判断能不能入队,                 if (edge[poll][i] != -1) {                     //更新                     if (dis[i] == INF || dis[i] > dis[poll] + edge[poll][i]) {                         dis[i] = dis[poll] + edge[poll][i];                     }                     if (!vis[i]) {                         vis[i] = true;                         queue.offer(i);                     }                 }                  */                 int w = g[poll][next];                 if (w != -1 && (dis[next] == INF || dis[next] > dis[poll] + w)) {                     dis[next] = dis[poll] + w;                     // 如果队列中没有,就可以入队,不要重复入队                     if (!vis[next]) {                         vis[next] = true;                         queue.offer(next);                     }                 }             }         }          int res = Arrays.stream(dis).max().getAsInt();         return res == INF ? -1 : res;     } }

Floyd

  • 由于是动态规划,所以都是用邻接矩阵
  • 并且它是不用 dis 数组和 vis 数组的
  • 这边注意,初始化邻接矩阵的时候,如果两个顶点没有边,最好初始化为INF,别初始化为-1,这也是我提交时候注意到的,上面说过Floyd是不能处理负权边的,只能判断有没有负环!
public class Solution {      private int INF = 0x3f3f3f3f;      public int networkDelayTime(int[][] times, int N, int K) {         int[][] g = new int[N + 1][N + 1];         // 初始化图,注意,一开始距离是初始化为INF的,而不是像 spfa初始化成-1         // spfa初始化成-1只是为了判断是否为邻居,这里初始化为INF是因为要取min的         for (int i = 1; i <= N; i++) {             for (int j = 1; j <= N; j++) {                 g[i][j] = i == j ? 0 : 0x3f3f3f3f;             }         }         for (int[] t : times) {             g[t[0]][t[1]] = t[2];         }         // 使用K节点来松弛i->j的最短路径(大白话就是利用k作为中间节点)         for (int k = 1; k <= N; k++) {             for (int i = 1; i <= N; i++) {                 for (int j = 1; j <= N; j++) {                     // 判断语句不用写                     // if (k != i && k != j && g[i][k] != INF && g[k][j] != INF) {                         g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);                     // }                 }             }         }         // g[a][b]表示a到b的最短距离         //拿结果         int res = 0;         for (int distance : g[K]) {             res = Math.max(res, distance);         }         return res == INF ? -1 : res;     } }


算法

程序员修炼之道读书笔记补上前言 一直有个读书的计划,每一年都是懒过去了,白稚卿说的很对,能战胜懒的只有ddl和绝对的自律,在学校里也只有老师要求写读书笔记才会去翻阅一下了,在学校各种压力都很大,大家选择解压的方式各不相同,我也开始尝试读一些
2020-03-19 随笔
线程池源码整体架构 首先来了一个任务,先判断下核心线程池里的线程数有没有达到设定的值,如果没有,就可以新建个Worker出来处理任务,处理任务的时候如果这个任务为空,那这个worker就阻塞住,因为这个任务不需要处理,如果这个任务不为空,
2020-03-01 Java集合源码

本文地址https://www.b2bchain.cn/?p=6056

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 算法-最短路
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们