关于最短路径几种算法的总结_最短路径算法

一、Dijkstra 算法

1. 迪杰斯特拉算法，可以解决无负权值的单源最短路径问题。
2. 基本思路是对图 G(V, E) 设置集合 S ，存放已被访问的顶点，然后每次从集合 V - S 中选择与起点 s 的最短距离最小的一个顶点（记为 u ），访问并加入集合 S。之后，令顶点 u 为中介点，优化起点 s 与所有从 u 能到达的顶点 v 之间的最短距离。这样操作 n 次（ n 为顶点个数），直到集合 S 已包含所有顶点。
3. 邻接矩阵版的 Dijkstra 算法，复杂度为 $O\left ( V^{2} \right )$（ V 为顶点个数）。

4. const int MAXN = 1000;
   const int INF = 0x3fffffff;

   int n, G[MAXN][MAXN]; // n 为顶点数，MAXN 为最大顶点数
   int d[MAXN]; //起点到达各点的最短路径长度
   bool vis[MAXN] = { false }; //标记数组，标记顶点是否被访问过

   void dijkstra(int s) { // s 为起点
       fill(d, d + MAXN, INF); // 初始化 d 数组为 INF
       d[s] = 0; //起点 s 到达自身的距离为 0
       for (int i = 0; i < n; i++) { //循环 n 次
           int u = -1, MIN = INF; // u 使 d[u] 最小，MIN 存放该最小的 d[u]
           for (int j = 0; j < n; j++) //找到未访问的顶点中 d[] 最小的
               if (!vis[j] && d[j] < MIN) { u = j; MIN = d[j]; }
           if (u == -1) return; //找不到小于 INF 的 d[u]，说明剩下的顶点和起点 s 不连通
           vis[u] = true; //标记 u 为已访问
           for (int v = 0; v < n; u++)
               //如果 v 未访问，且 u->v 连通，且以 u 为中介点可使 d[v] 更优
               if (!vis[u] && G[u][v] != INF && d[u] + G[u][v] < d[v])
                   d[v] = d[u] + G[u][v]; //优化 d[v]
       }
   }

5.  邻接表版的 Dijkstra 算法，复杂度为 $O\left ( V^{2} + E\right )$。

6. const int MAXN = 1000;
   const int INF = 0x3fffffff;

   struct node { int v, dis; };
   vector <node> adj[MAXN]; // adj[u] 存放从顶点 u 出发可以到达的所有顶点
   int n; // n 为顶点数
   int d[MAXN]; //起点到达各点的最短路径长度
   bool vis[MAXN] = { false }; //标记数组，标记顶点是否被访问过

   void dijkstra(int s) { // s 为起点
       fill(d, d + MAXN, INF); // 初始化 d 数组为 INF
       d[s] = 0; //起点 s 到达自身的距离为 0
       for (int i = 0; i < n; i++) { //循环 n 次
           int u = -1, MIN = INF; // u 使 d[u] 最小，MIN 存放该最小的 d[u]
           for (int j = 0; j < n; j++) //找到未访问的顶点中 d[] 最小的
               if (!vis[j] && d[j] < MIN) { u = j;    MIN = d[j]; }
           if (u == -1) return; //找不到小于 INF 的 d[u]，说明剩下的顶点和起点 s 不连通
           vis[u] = true; //标记 u 为已访问
           for (int j = 0; j < adj[u].size(); j++) {
               int v = adj[u][j].v; //通过邻接表直接获得 u 能到达的顶点 v
               //如果 v 未访问，且以 u 为中介点可使 d[v] 更优
               if (!vis[v] && d[u] + adj[u][j].dis < d[v])
                   d[v] = d[u] + adj[u][j].dis; //优化 d[v]
           }
       }
   }

7. 可以使用堆（优先级队列）来优化寻找最小 d[u] 的过程，这样使用邻接矩阵实现的 Dijkstra 算法的时间复杂度可以降为 $O\left ( VlogV \right )$​​​，使用邻接表实现的 Dijkstra 算法的时间复杂度可以降为 $O\left ( VlogV+E \right )$。 
8. 如果要求得最短路径本身，可以设置数组 pre[]，令 pre[v] 表示从起点 s 到顶点 v 的最短路径上 v 的前一个顶点（即前驱结点）的编号，这样可以在优化 d[v] 时，可以将 u 赋给 pre[v]，最终就能把最短路径上每一个顶点的前驱记录下来。然后使用 DFS 递归便可以输出最短路径本身。

9. 一般情况下，如果有两条及以上可以达到最短距离的路径，题目会给出一个第二标尺（第一标尺是距离），要求在所有最短路径中选择第二标尺最优的一条路径。而第二标尺常见的是这三种情况或其组合：第一种，给每条边再增加一个边权（比如花费），然后要求在最短路径有多条时要求路径上的花费之和最小（如果边权是其他含义，也可以是最大）；第二种，给每个点增加一个点权（例如每个城市能收集到的物资），然后在最短路径有多条时要求路径上的点权之和最大（如果点权是其他含义的话也可以是最小）；第三种，直接问有多少条最短路径。对于这三种出题方法，都只需要增加一个数组来存放新增的边权或点权或最短路径条数，然后在优化 d[v] 的那个步骤中修改增加的数组即可。

10. 这里给出一种通用的模板化的解决上述三种情况的最短路径算法：Dijkstra + DFS。具体是先在 Dijkstra 算法中记录下所有最短路径（只考虑距离），然后从这些最短路径中选出一条第二标尺最优的路径。完整的参考代码如下。

11. const int MAXN = 1000;
    const int INF = 0x3fffffff;

    第一步，使用 Dijkstra 算法记录所有的最短路径
    int n, G[MAXN][MAXN];
    int d[MAXN];
    bool vis[MAXN] = { false };
    vector <int> pre[MAXN];

    void dijkstra(int s) {
        fill(d, d + MAXN, INF);
        d[s] = 0;
        for (int i = 0; i < n; i++) {
            int u = -1, MIN = INF;
            for (int j = 0; j < n; j++)
                if (!vis[j] && d[j] < MIN) { u = j; MIN = d[j]; }
            if (u == -1) return;
            vis[u] = true;
            for (int v = 0; v < n; v++)
                if (!vis[v] && G[u][v] != INF) {
                    if (d[u] + G[u][v] < d[v]) {
                        d[v] = d[u] + G[u][v]; //优化 d[v]
                        pre[v].clear(); //清空 pre[v]
                        pre[v].push_back(u); //令 v 的前驱为 u
                    }
                    else if (d[u] + G[u][v] == d[v]) {
                        pre[v].push_back(u); //令 v 的前驱为 u
                    }
                }
        }
    }

    第二步，遍历所有最短路径，找出一条使第二标尺最优的路径
    int opt_value; //第二标尺最优值
    int st; //路径的起点
    vector <int> path, temp_path; //最优路径，临时路径

    void DFS(int v) {
        if (v == st) { //如果到达了路径起点
            temp_path.push_back(v); //将起点加入临时路径 temp_path 的最后面
            int value = 0; //存放临时路径 temp_path 的第二标尺的值
            计算路径 temp_path 上的 value 值
            if (value 优于 opt_value) {
                opt_value = value; //更新第二标尺最优值
                path = temp_path; //更新最优路径
            }
            temp_path.pop_back(); //将刚加入的结点删除
            return;
        }
        //递归式
        temp_path.push_back(v); //将当前访问结点加入临时路径 temp_path 的最后面
        for (int i = 0; i < pre[v].size(); i++) 
            DFS(pre[v][i]); //结点 v 的前驱结点 pre[v][i]，递归
        temp_path.pop_back(); //遍历完所有前驱结点，将当前结点 v 删除
    }

12. 注意。由于递归的原因，存放在 temp_path 中的路径结点是逆序的，因此访问结点需要倒着进行；另外，顶点下标的范围需要根据题意来考虑是 0 ~ n-1 还是 1 ~ n。

二、Bellman-Ford 算法

1. Bellman-Ford 算法可以解决有负权值的单源最短路径问题。与 Dijkstra 算法相同，Bellman-Ford 算法设置一个数组 d ，用来存放从源点到达各个顶点的最短距离。同时 Bellman-Ford 算法返回一个 bool 值：如果其中存在从源点可达的负环，那么函数将返回 false；否则，函数将返回 true，此时数组 d 中存放的值就是从源点到达个顶点的最短距离。
2. Bellman-Ford 算法的思路是对图中的边进行 V-1 轮操作，每轮都遍历图中的所有边：对每条边 u->v，如果以 u 为中介点可以使 d[v] 更小，就更新 d[v]。此时，如果图中没有从源点可达的负环，那么数组 d 中的所有值都应当已经达到最优。因此，只需要再对所有边进行一轮操作，判断是否有某个中介点可以使得 d[v] 可以更小，如果有，则说明图中有从源点可达的负环，返回 false；否则，说明数组 d 中的所有值已经达到最优，返回 true。算法的时间复杂度为 $O\left ( VE \right )$（ V 为顶点个数，E 为边数）。
3. 由于 Bellman-Ford 算法需要遍历所有边，因此使用邻接表会比较方便。参考代码如下。

4. struct node { int v, dis; }; // v 为邻接边的目标顶点， dis 为邻接边的边权
   int n; // n 为顶点数，MAXN 为最大顶点数
   vector <node> adj[MAXN]; //图的邻接表
   int d[MAXN]; //起点到达各点的最短路径长度

   bool bellman(int s) { // s 为源点
       fill(d, d + MAXN, INF);
       d[s] = 0; //起点 s 到达自身的距离为 0
       //以下为求解数组 d 的部分
       for (int i = 0; i < n - 1; i++) { //执行 n-1 轮操作，n 为顶点数
           for (int u = 0; u < n; u++) { //每轮操作都遍历所有边
               for (int j = 0; j < adj[u].size(); j++) {
                   int v = adj[u][j].v; //邻接边的顶点
                   int dis = adj[u][j].dis; //邻接边的边权
                   if (d[u] + dis < d[v]) //以 u 为中介点可以使 d[v] 更小
                       d[v] = d[u] + dis; //松弛操作
               }
           }
       }
       //以下为判断负环的代码
       for (int u = 0; u < n; u++) { //对每条边进行判断
           for (int j = 0; j < adj[u].size(); j++) {
               int v = adj[u][j].v; //邻接边的顶点
               int dis = adj[u][j].dis; //邻接边的边权
               if (d[u] + dis < d[v]) //如果仍可以被松弛
                   return false; //说明图中存在从源点可达的负环
           }
       }
       return true; //数组 d 的所有值已经达到最优
   }

5. 最短路径的求解方法、有多重标尺时的做法均与 Dijkstra 算法中介绍的相同。唯一要注意的是统计最短路径条数的做法：需要设置记录前驱的数组 set <int> pre[MAXN]，当遇到一条和已有最短路径长度相同的路径时，必须重新计算最短路径条数。 

三、SPFA 算法

1. Bellman-Ford 算法的每轮操作都需要操作所有边，显然这其中会有大量无意义的操作，严重影响了算法的性能。注意到只有当某个顶点 u 的 d[u] 值改变时，从它出发的边的邻接点 v 的 d[v] 值才有可能被改变。因此进行一个优化：建立一个队列，每次将队首顶点 u 取出，然后对从 u 出发的所有边 u->v 进行松弛操作，如果 d[v] 获得了更优的值，此时如果 v 不在队列中，就把 v 加入队列。这样操作直到队列为空（说明图中没有从源点可达的负环），或是某个顶点的入队次数超过 V-1 （说明图中存在从源点可达的负环）。
2. 这种优化后的算法被称为 SPFA（Shortest Path Faster Algorithm），期望时间复杂度为 $O\left ( kE \right )$，其中 E 是图的边数，k 是一个常数，很多情况下都不超过 2 ，但如果图中有从源点可达的负环，传统 SPFA 的时间复杂度就会退化成 $O\left ( VE \right )$。
3. 如果事先知道图中不会有环，那么 num 数组的部分可以去掉。注意，使用 SPFA 算法可以判断是否存在从源点可达的负环，如果负环从源点不可达，则需要添加一个辅助顶点 C ，并添加一条从源点到达 C 的有向边以及 V-1 条从 C 到达从 C 到达除源点外各顶点的有向边才能判断负环是否存在。参考代码如下。

4. struct node { int v, dis; }; // v 为邻接边的目标顶点， dis 为邻接边的边权
   int n; // n 为顶点数，MAXN 为最大顶点数
   vector <node> adj[MAXN]; //图的邻接表
   int d[MAXN], num[MAXN] = { 0 }; //d 记录起点到达各点的最短路径长度，num 记录顶点的入队次数
   bool inq[MAXN] = { false }; //顶点是否在队列中

   bool SPFA(int s) {
       fill(d, d + MAXN, INF);
       queue <int> q;
       q.push(s); //源点入队
       inq[s] = true; //源点已入队
       num[s]++; //源点入队次数加 1
       d[s] = 0; //源点的 d 值为 0
       while (q.size()) {
           int u = q.front(); //队首顶点编号为 u
           q.pop(); //出队
           inq[u] = false; //设置 u 不在队列中
           for (int j = 0; j < adj[u].size(); j++) { //遍历 u 的所有邻接边 v
               int v = adj[u][j].v;
               int dis = adj[u][j].dis;
               if (d[u] + dis < d[v]) { //松弛操作
                   d[v] = d[u] + dis;
                   if (!inq[v]) { //如果 v 不在队列中
                       q.push(v); // v 入队
                       inq[v] = true; //设置 v 为在队列中
                       num[v]++; // v 的入队次数加 1
                       if (num[v] > n - 1) return false; //有可达负环
                   }
               }
           }
       }
       return true; //无可达负环
   }

5. SPFA 十分灵活，其内部的写法可以根据具体场景的不同进行调整。上面给出的代码是 SPFA 的 BFS 版本，如果将队列替换成栈，则可以实现 DFS 版本的 SPFA ，对判环有奇效。

四、Floyd 算法

1. Floyd 算法（弗洛伊德算法）用来解决全源最短路径问题，即对给定的图 G(V, E) ，求任意两点 u，v 之间的最短路径长度，时间复杂度为 $O\left ( n^{3} \right )$。此时间复杂度限定了顶点数 n 约在200以内，因此使用邻接矩阵来实现 Floyd 算法是非常合适且方便的。
2. Floyd 算法的基本思路：如果存在顶点 k，使得以 k 为中介点时顶点 i 和顶点 j 的当前距离缩短，则使用顶点 k 作为顶点 i 和顶点 j 的中介点。这样枚举所有的顶点 k，以顶点 k 为中介点，枚举所有的顶点对 i 和 j，进行优化即可。参考代码如下。

3. int n, m; // n 为顶点数，m 为边数
   int dis[MAXN][MAXN]; // dis[i][j] 表示顶点 i 和顶点 j 的最短距离

   void floyd() {
       for (int k = 0; k < n; k++)
           for (int i = 0; i < n; i++)
               for (int j = 0; j < n; j++)
                   if (dis[i][k] != INF && dis[k][j] != INF && dis[i][k] + dis[k][j] < dis[i][j])
                       dis[i][j] = dis[i][k] + dis[k][j]; //找到更短的路径
   }

五、总结

六、参考文献 

[1] 胡凡,曾磊.算法笔记[M].机械工业出版社,2016:465.