最短路

1 简介

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

• 单源 Dijkstra算法：
  • 优点：时间复杂度稳定$O(n^2)$，堆优化能达到$O(ElogE)$；也可解决多源最短路，总的时间复杂度也是$O(n^3)$
  • 缺点：不能处理负边
• 单源 Bellman-Ford算法：
  • 优点：其优于Dijkstra算法的方面是边的权值可以为负数、实现简单
  • 缺点：时间复杂度过高，高达$O(V*E)$；但算法可以进行若干种优化，提高了效率。
• 单源 SPFA算法：
  • 优点：快于Bellman-Ford，据说随机数据下期望时间复杂度是$O(m+nlogn)$
  • 缺点：时间复杂度不稳定，最坏情况可以被卡成Bellman-Ford，也就是$O(V*E)$
• 全源 Floyd算法：
  • 优点：算法简洁，可以解决负权图
  • 缺点：时间复杂度为$O(n^3)$，空间复杂度为$O(n^2)$，都比较高，所以只适用于数据规模较小的情形；不能解决负环图
• 全源 Johnson算法：
  • 优点：相对于Floyd算法时间复杂度低，$O(nmlogm)$；
  • 缺点：无负环图、算法较繁琐
• BFS算法：
  • 优点：
  • 缺点：只能解决无权图

2 单源 Dijkstra算法

贪心的思想，不断取出离顶点最近而没有被访问过的点，松弛它和它能到达的所有点。

对于每个顶点v∈V，都设置一个属性d[v]，用来描述从源点s到v的最短路径上权值的上界，称为最短路径估计（shortest-pathestimate）。

π[v]代表S到v的当前最短路径中v点之前的一个点的编号,我们用下面的Θ(V)时间的过程来对最短路径估计和前趋进行初始化。

在松弛一条边(u,v)的过程中，要测试是否可以通过u，对迄今找到的v的最短路径进行改进；如果可以改进的话，则更新d[v]和π[v]。一次松弛操作可以减小最短路径估计的值d[v]，并更新v的前趋域π[v](S到v的当前最短路径中v点之前的一个点的编号)。

打印路径：只需要用一个pre[]数组存储每个点的父节点即可。（单源最短路的起点是固定的，所以每条路有且仅有一个祖先节点，一步步溯源上去的路径是唯一的。相反，这里不能存子节点，因为从源点下去，有很多条最短路径）

参考：https://zhuanlan.zhihu.com/p/96621396

朴素Dijkstra：时间复杂度是 $O(n^2+m)$, $n$ 表示点数，$m$ 表示边数

const int maxn = 5e2 + 5;

int g[maxn][maxn];  // 存储每条边
int dist[maxn];  // 存储1号点到每个点的最短距离
bool st[maxn];   // 存储每个点的最短路是否已经确定
int n;//点数
 
// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ ) {
        int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

堆优化Dijkstra：时间复杂度 $O(mlogn)$, $n$ 表示点数，$m$ 表示边数

const int maxn = 1.5e5 + 5;
typedef pair<int, int> PII;

int n;      // 点的数量
int h[maxn], w[maxn], e[maxn], ne[maxn], idx;  // 邻接表存储所有边
int dist[maxn];        // 存储所有点到1号点的距离
bool st[maxn];     // 存储每个点的最短距离是否已确定
//加边
void add(int x, int y, int c) {
    w[idx] = c; // 有重边也不要紧，假设1->2有权重为2和3的边，再遍历到点1的时候2号点的距离会更新两次放入堆中
    e[idx] = y; // 这样堆中会有很多冗余的点，但是在弹出的时候还是会弹出最小值2+x（x为之前确定的最短路径），并
    ne[idx] = h[x]; // 标记st为true，所以下一次弹出3+x会continue不会向下执行。
    h[x] = idx++;
}
// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});      // first存储距离，second存储节点编号

    while (heap.size()) {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > distance + w[i]) {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

3 单源 Bellman-Ford算法

一维数组dist[]来存储每个点到起点的距离，初始化dist[S] = 0，其他初始化为INF。

找到从起点到某个点的最短路，设起点为S，终点为D，那这条最短路一定是$S->P_1->P_2->...->D$的形式，假设没有负权环，那这条路径上的点的总个数一定不大于n。

定义对点x, y的松弛操作是：

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

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

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

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

把所有边松弛n-1遍！

https://zhuanlan.zhihu.com/p/96621396

https://blog.csdn.net/luomingjun12315/article/details/50377525

4 单源 SPFA算法

SPFA算法，也就是队列优化的Bellman-Ford算法，维护一个队列。

5 全源 Floyd算法

求出每一对顶点之间的最短路径。Floyd本质上是一个动态规划的思想，每一次循环更新经由k点，i到j的最短路径。

// 算法结束后，d[a][b]表示a到b的最短距离，path存放路径信息
void floyd() {
	//	初始化：
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
            else d[i][j] = inf;
    //memset(path, -1, sizeof path);
    
	//dp 
    for (int k = 1; k <= n; k ++ ) {//考虑以k为中转点
        for (int i = 1; i <= n; i ++ ) {
        	for (int j = 1; j <= n; j ++ ) {
                if (d[i][j] > d[i][k] + d[k][j]) {//以k为中转点的路径更短
                	d[i][j] = d[i][k] + d[k][j];//更新最短路径长度
                    //path[i][j] = k;//中转点
                }     
            } 
        }
    } 
}

6 全源 Johnson算法

7 BFS算法

该算法求单源最短路径只适用于无权图，或所有边的权值都相同的图。

练习

1. acwing模板题目——Dijkstra求最短路 I
2. Dijkstra求最短路 II