算法笔记【7】最短路问题

雨点打透心脏的1/2处 2023-01-11 13:02 185阅读 0赞

# 算法笔记【7】 最短路问题 #

## 最短路问题简介 ##

这篇文章应该会很长，因为我们要探讨图论中一个基本而重要的问题：**最短路问题**。如下图，我们想知道，**某点到某点最短的路径有多长**？

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center]

最短路问题分为两类：**单源最短路**和**多源最短路**。前者只需要求一个**固定的起点**到各个顶点的最短路径，后者则要求得出**任意两个顶点**之间的最短路径。我们先来看多源最短路问题。

## Floyd算法(弗洛伊德算法) ##

我们用Floyd算法解决多源最短路问题：

public static int[][] floyd(int[][] e) { 
        for (int k = 0; k < e.length; k++) { 
            for (int i = 0; i < e.length; i++) { 
                if (i == k) continue;
                for (int j = 0; j < e.length; j++) { 
                    if (e[i][j] > e[i][k] + e[k][j]) { 
                        e[i][j] = e[i][k] + e[k][j];
                    }
                }
            }
        }
        return e;
    }

几行代码，简洁明了。Floyd本质上是一个**动态规划**的思想，每一次循环更新**经过前k个节点，i到j的最短路径**。

这甚至不需要特意存图，因为dist数组本身就可以从邻接矩阵拓展而来。初始化的时候，我们把每个点**到自己的距离**设为0，每新增一条边，就把从这条边的起点到终点的距离设为此边的**边权**（类似于邻接矩阵）。其他距离初始化为**INF**（一个超过边权数据范围的大整数，注意防止溢出）。

public class Arithmetic7 { 
        public static void main(String[] args) { 
            int[][] map = new int[][]{ { 0, 2, 6, 4},
                    { Integer.MAX_VALUE, 0, 3, Integer.MAX_VALUE},
                    { 7, Integer.MAX_VALUE, 0, 1},
                    { 5, Integer.MAX_VALUE, 12, 0}};
            int[][] floyd = floyd(map);
            System.out.println(floyd[3][2]);
        }
    
        public static int[][] floyd(int[][] e) { 
            for (int k = 0; k < e.length; k++) { 
                for (int i = 0; i < e.length; i++) { 
                    if (i == k) continue;
                    for (int j = 0; j < e.length; j++) { 
                        if (e[i][j] > e[i][k] + e[k][j]) { 
                            e[i][j] = e[i][k] + e[k][j];
                        }
                    }
                }
            }
            return e;
        }
    
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 1]

如果你还是没懂，现在我们来看Floyd的具体过程。

第一趟，k=1：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 2]

很明显，没有一个距离能通过经由1号点而减短。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 3]

这里，dist\[1\]\[4\]通过经由2号点，最短路径缩短了。

第三趟，k=3：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 4]

这时虽然1->3->4的路径比1->4短，但是dist\[1\]\[4\]已经被更新为3了，所以这一趟又白跑了。接下来k=4显然也更新不了任何点。综上，每一趟二重循环，实际上都是在考察，**能不能经由k点，把i到j的距离缩短**？

Floyd的时间复杂度显然是 O(n^3) ，同时拥有 O(n^2) 的空间复杂度（本文用n表示点数，m表示边数），都比较高，所以只适用于数据规模较小的情形。

一般而言，我们更关心的是**单源最短路**问题，因为当起点被固定下来后，我们可以使用更快的算法。

## Bellman-Ford算法（贝尔曼-福特算法） ##

因为起点被固定了，我们现在只需要一个一维数组dist\[\]来存储每个点到起点的距离。如下图，1为起点，我们初始化时把dist\[1\]初始化为1，其他初始化为INF。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 5]

想想看，我们要找到从起点到某个点的最短路，设起点为S，终点为D，那这条最短路一定是**S->P1->P2->…->D**的形式，假设**没有负权环**，那这条路径上的点的总个数一定**不大于n**。

现在我们定义对点x, y的**松弛**操作是：

//这里的e[x][y]表示x、y之间的距离，具体形式可能根据存图方法不同而改变
    dist[y] = Math.min(dist[y], dist[x] + e[x][y]);

松弛操作就相当于考察能否**经由x点**使**起点到y点**的距离变短。

所以要找到最短路，我们只需要进行以下步骤：

1.  先松弛S, P1，此时dist\[P1\]必然等于e\[S\] \[P1\]。
2.  再松弛P1, P2，因为S->P1->P2是最短路的一部分，**最短路的子路也是最短路**（这是显然的），所以dist\[P2\]不可能小于dist\[P1\]+e\[P2\]，因此它会被更新为dist\[P1\]+e\[P2\]，即e\[S\]+e\[P1\]。
3.  再松弛P2, P3，……以此类推，最终dist\[D\]必然等于e\[S\] \[P1\]+e\[P1\]+…，这恰好就是最短路径。

说得好像很有道理，但是问题来了，我怎么知道这些P1、P2是什么呢？我们不就是要找它们吗？关键的来了，Bellman-Ford算法告诉我们：

**把所有边松弛一遍！**

因为我们要求的是最小值，而多余的松弛操作不会使某个dist比最小值还小。所以**多余的松弛操作不会影响结果**。把所有边的端点松弛完一遍后，我们可以保证S, P1已经被松弛过了，现在我们要松弛P1, P2，怎么做呢？

**再把所有边松弛一遍！**

好了，现在我们松弛了P1, P2，继续这么松弛下去，什么时候是尽头呢？还记得我们说过吗？最短路上的点的总个数一定**不大于n**，尽管一般而言最短路上的顶点数比n少得多，但反正多余的松弛操作不会影响结果，我们索性：

**把所有边松弛n-1遍！**

这就是Bellman-Ford算法，相信你已经意识到，这是种很暴力的算法，它的时间复杂度是 O(mn) 。代码如下：

public static int[] bellmanFord() { 
        //接点数
        int n = 4;
        //边数量
        int m = 5;
        Graph2 graph2 = new Graph2(n, m);
        graph2.add(0, 1, 1);
        graph2.add(0, 2, 4);
        graph2.add(0, 3, 6);
        graph2.add(1, 3, 2);
        graph2.add(2, 3, 1);
        Graph2.Edge[] edges = graph2.edges;
        int[] dist = new int[n];
        for (int i = 1; i < dist.length; i++) { 
            dist[i] = Integer.MAX_VALUE;
        }
        for (int j = 0; j < n - 1; ++j) { 
            for (int i = 0; i < edges.length - 1; ++i) { 
                dist[edges[i].to] = Math.min(dist[edges[i].to], dist[edges[i].from] + edges[i].w);
            }
        }
        return dist;
    }

几行代码，比Floyd还简单。这里用的是链式前向星存图，但是建议存的时候多存一个from，方便遍历所有边。当然其实并没什么必要，这里直接**暴力存边集**就可以了，因为这个算法并不关心每个点能连上哪些边。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 6]

很显然我这个图太简单了一点，只遍历了一遍所有边，就把所有最短路求出来了。但为了保证求出正解，还需要遍历两次。

我们之前说，我们不考虑**负权环**，但其实Bellman-Ford算法是可以很简单地处理负权环的，只需要再**多对每条边松弛一遍**，如果这次还有点被更新，就说明存在负权环。因为没有负权环时，最短路上的顶点数一定小于n，而存在负权环时，可以无数次地环绕这个环，最短路上的顶点数是无限的。

## SPFA算法 ##

O(mn)的复杂度显然还是太高了，现在我们想想，能不能别这么暴力，每次不松弛所有点，而只松弛**可能更新**的点？

我们观察发现，第一次松弛S, P1时，可能更新的点只可能是**S能直接到达的点**。然后下一次可能被更新的则是**S能直接到达的点能直接到达的点**。SPFA算法正是利用了这种思想。

**SPFA算法**，也就是**队列优化**的Bellman-Ford算法，维护一个队列。一开始，把起点放进队列：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 7]

我们现在考察1号点，它可以到达点2、3、4。于是1号点出队，2、3、4号点依次入队，入队时松弛相应的边。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 8]

现在队首是2号点，2号点出队。2号点可以到达4号点，我们松弛2, 4，但是4号点**已经在队列里**了，所以4号点就不入队了（之后解释原因）。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 9]

因为这张图非常简单，后面的流程我就不画了，无非是3号点出队，松弛3, 4，然后4号点出队而已。当队列为空时，流程结束。

为了表明SPFA的优越性，我们再来看一个稍微复杂一点的图（在原图基础上增加一个5号点）：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 10]

这张图，按照Bellman-Ford算法，需要松弛8\*4=32次。现在我们改用SPFA解决这个问题。

显然前几步跟上次是一致的，我们松弛了1, 2、1, 3、1, 4，现在队首元素是2。我们让2出队，并松弛2, 4、2, 5。5未在队列中，5入队。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 11]

3号点没能更新什么东西：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 12]

然后4号点出队，松弛4, 5，然后5号点已在队列所以不入队。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 13]

最后5号点出队，dist\[3\]**未被更新**，所以3号点通往的点**不会跟着被更新**，因此3号点不入队，循环结束。

这个过程中，我们只进行了**6次松弛**，远小于B-F算法的32次，虽然进行了入队和出队，但在n、m很大时，SPFA通常还是显著快于B-F算法的。·（据说随机数据下期望时间复杂度是 O(m+nlogn)总结一下，SPFA是如何做到“只更新可能更新的点”的？

1.  **只让当前点能到达的点入队**
2.  如果一个点**已经在队列**里，便**不重复入队**
3.  如果一条边**未被更新**，那么它的终点不入队

原理是，我们的目标是松弛完 S->P1-> P2 ->······D ，所以我们先把 S 能到达的所有点加入队列，则 P1 一定在队列中。然后对于队列中每个点，我们都把它能到达的所有点加入队列（不重复入队），这时我们又可以保证 P2 一定在队列中。另外注意到，假如 Pi -> Pi+1是目标最短路上的一段，那么在松弛这条边时它一定是会被更新的，所以如果一条边未被更新，它的终点就不入队。

我们用一个flag\[\]数组来记录一个点是否在队列里，于是SPFA的代码如下：

public static int[] spfa() { 
        int n = 7;
        int m = 12;
        //先用链式向前星存图
        Graph2 graph2 = new Graph2(n, m);
        graph2.add(0, 1, 24);
        graph2.add(0, 2, 8);
        graph2.add(0, 3, 15);
        graph2.add(1, 4, 6);
        graph2.add(2, 4, 7);
        graph2.add(2, 5, 3);
        graph2.add(3, 6, 4);
        graph2.add(4, 6, 9);
        graph2.add(5, 3, 5);
        graph2.add(5, 4, 2);
        graph2.add(5, 6, 3);
        graph2.add(6, 1, 3);
        Graph2.Edge[] edges = graph2.edges;
        int[] head = graph2.head;
    
        // 用于标记下标节点是否进入队列
        boolean[] flag = new boolean[n];
    
        // 初始化最短路径表
        int[] path = new int[n];
        for (int i = 1; i < path.length; i++) { 
            path[i] = Integer.MAX_VALUE;
        }
        //创建队列获取
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        //队列中放入第一个节点
        queue.add(0);
        //循环获取队列中的节点
        while (!queue.isEmpty()) { 
            Integer poll = queue.poll();
            for (int e = head[poll]; e != -1; e = edges[e].next) { 
                int to = edges[e].to;
                int from = edges[e].from;
                int w = edges[e].w;
                //队列中没有就加入队列
                if (!flag[to]) { 
                    queue.add(to);
                    flag[to] = true;
                }
                //比较路径距离
                if (path[to] > path[from] + w) { 
                    path[to] = path[from] + w;
                }
            }
        }
        return path;
    }

这个算法已经可以A掉洛谷P3371的单源最短路径（弱化版）了。然而它的时间复杂度**不稳定**，最坏情况可以被卡成Bellman-Ford，也就是O(mn) 。现在不少最短路的题会刻意卡SPFA，所以会有大佬说：SPFA死了。然而这仍然不失为一种比较好写、通常也比较快的算法。

SPFA也可以判负权环，我们可以用一个数组记录每个顶点进队的次数，当一个顶点**进队超过n次**时，就说明存在负权环。（这与Bellman-Ford判负权环的原理类似）

## Dijkstra算法(迪杰斯特拉算法) ##

Dij基于一种**贪心**的思想，我们假定有一张没有**负边**的图。首先，起点到起点的距离为0，这是没有疑问的。现在我们对起点和它能直接到达的所有点进行松弛。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 14]

因为没有负边，这时我们可以肯定，**离起点最近的那个顶点的dist一定已经是最终结果**。为什么？因为没有负边，所以不可能经由其他点，使起点到该点的距离变得更短。

那现在我们来考察2号点：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 15]

我们对2号点和它能到达的点进行松弛。这时dist保存的是起点**直接到达**或**经由2号点到达**每个点的最短距离。我们这时候取出未访问过的dist最小的点（即4号点），这个点的dist也不可能变得更短了（因为其他路径都至少要从起点直接到达、或者经由2号点到达另一个点，再从这另一个点到达4号点）。

继续这个流程，松弛4号点能到达的点：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 16]

然后分别考察3、5号点，直到所有点都被访问过即可。

总结一下，Dijkstra算法的流程就是，不断取出**离顶点最近**而**没有被访问过**的点，松弛它和它能到达的所有点。

代码如下

/** * Dijkstra 算法 */
    public static int[] dijkstra(int[][] weight, int start) { 
        // 接受一个有向图的权重矩阵，和一个起点编号start（从0编号，顶点存在数组中）
        // 返回一个int[] 数组，表示从start到它的最短路径长度
        int n = weight.length; // 顶点个数
        int[] shortPath = new int[n]; // 保存start到其他各点的最短路径
        String[] path = new String[n]; // 保存start到其他各点最短路径的字符串表示
        for (int i = 0; i < n; i++)
            path[i] = new String(start + "-->" + i);
        int[] visited = new int[n]; // 标记当前该顶点的最短路径是否已经求出,1表示已求出
    
        // 初始化，第一个顶点已经求出
        shortPath[start] = 0;
        visited[start] = 1;
    
        for (int count = 1; count < n; count++) {  // 要加入n-1个顶点
            int k = -1; // 选出一个距离初始顶点start最近的未标记顶点
            int dmin = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) { 
                if (visited[i] == 0 && weight[start][i] < dmin) { 
                    dmin = weight[start][i];
                    k = i;
                }
            }
    
            // 将新选出的顶点标记为已求出最短路径，且到start的最短路径就是dmin
            shortPath[k] = dmin;
            visited[k] = 1;
    
            // 以k为中间点，修正从start到未访问各点的距离
            for (int i = 0; i < n; i++) { 
                //如果 '起始点到当前点距离' + '当前点到某点距离' < '起始点到某点距离', 则更新
                if (visited[i] == 0 && weight[start][k] + weight[k][i] < weight[start][i]) { 
                    weight[start][i] = weight[start][k] + weight[k][i];
                    path[i] = path[k] + "-->" + i;
                }
            }
        }
        for (int i = 0; i < n; i++) { 
    
            System.out.println("从" + start + "出发到" + i + "的最短路径为：" + path[i]);
        }
        return shortPath;
    }

\--------------最后感谢大家的阅读，愿大家技术越来越流弊！--------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70]

\--------------也希望大家给我点支持，谢谢各位大佬了！！！--------------

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center]: /images/20221119/76ebfa125dab4ef0991dad4bddf73f52.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221119/25921c443e1a48868cb208b30ce40915.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20210126225356625.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20210126225344509.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/2021012622533435.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20210126225319667.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/20210126225302303.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 7]: https://img-blog.csdnimg.cn/20210126225247121.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 8]: https://img-blog.csdnimg.cn/20210126225233956.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 9]: https://img-blog.csdnimg.cn/20210126225220143.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 10]: https://img-blog.csdnimg.cn/20210126225207620.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 11]: https://img-blog.csdnimg.cn/20210126225156789.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 12]: https://img-blog.csdnimg.cn/20210126225146580.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 13]: https://img-blog.csdnimg.cn/20210126225137780.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 14]: https://img-blog.csdnimg.cn/20210126225124723.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 15]: https://img-blog.csdnimg.cn/20210126225113464.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 16]: https://img-blog.csdnimg.cn/20210126225059854.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200721144257696.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70