求最短路径的基本算法

date
Jan 29, 2023
slug
short-path-problem
status
Published
tags
算法
summary
五种求最短路径的基本算法
type
Post
简介问题分类图的存储邻接矩阵邻接表单源最短路问题算法dijkstra 算法朴素版 dijkstra堆优化版 dijkstraBF 算法SPFA 算法负权回路对比 SPFA 和堆优化 dijkstraFloyd 算法总结参考

简介

最短路径问题要求我们给出点与点之间的最短路径，根据问题的分类一共有 5 种解决该类问题的方法。
本文将依次介绍每种算法的思想、时间复杂度、适用场景。
notion image

问题分类

最短路问题分为两类：
  1. 单源最短路：求两个点之间的最短路径，一般是 1 到 n 号点
  1. 多源汇最短路：求任意两个点之间的最短路径
 
而单源最短路问题，根据边的不同，又有一些需要注意的地方：
  1. 所有边权都是正数：这种情况是最常见的，用 dijkstra 就能求解
  1. 边权存在负数：此时 dijkstra 无法求解，只能使用 BF 或者 SPFA 算法求解
 

图的存储

邻接矩阵

最简单的存储方式
N是点数，一般不会太大，用于存储稀疏图
int g[N][N];

邻接表

又称为链式前向星
// 对于每个点k，开一个单链表，存储k所有可以走到的点。
// h[k]存储这个单链表的头节点
// e 存储 value， ne 存储 next 指针， w 存储边权
int h[N], e[N], ne[N], w[N], idx;

// 添加一条边 a -> b, 边权为 c
void add(int a, int b, int c)
{
		e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

// 遍历点t的所有出边
for (int i = h[t]; i != -1; i = ne[i]){
		distance = w[i]; // 边权
		// 具体操作
}

// 初始化
idx = 0;
memset(h, -1, sizeof h);

单源最短路问题算法

dijkstra 算法

该算法的思想是：
维护一个点集，每一轮找到一个离当前点集最近的一个点t，然后将t加入到点集中，同时用这个最近点去尝试更新其它未遍历点的距离，遍历n - 1轮即可得到答案。
伪代码：
dijkstra(){
		// dist[i] 表示从 1 号点出发到点 i 的最短路径
		for 遍历n-1轮：
			// 寻找最近点 O(n)
			for 遍历所有节点 j:
				如果当前点j没有确认最短路，并且距离最小：
					t = j，记录最近点是j
			
			// O(n)
			for 遍历所有点 j:
				// 尝试用 t 去更新其它点的距离，g是邻接矩阵
				// 如果 1 -> j 的距离大于 1 -> t -> j，更新最短路径为 1 -> t -> j 的距离
				dist[j] = min(dist[j], dist[t] + g[t][j]);
			
			标记 t 点已经确认最短路径
}
经过上面的计算，dist[n] 就是最终答案了。

朴素版 dijkstra

朴素版的 dijkstra 基本上是伪代码的实现，代码如下：
int g[N][N]; // 存储每条边
int dist[N]; // 存储1号点到每个点的最短距离
bool st[N];  // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路，如果不存在则返回-1 
int dijkstra()
{
		// 0x3f3f3f3f 表示无穷大
    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];
}
时间复杂度：，n是点数，m是边数
有关时间复杂度的计算可以参考这篇文章： Dijkstra算法时间复杂度分析
适用场景：稠密图，即点少但边多的场景，因此可以用邻接矩阵来存储图

堆优化版 dijkstra

在朴素版 dijkstra 中，下面的步骤：
  // 在还未确定最短路的点中，寻找距离最小的点
  int t = -1;
  for (int j = 1; j <= n; j++)
      if (!st[j] && (t == -1 || dist[t] > dist[j]))
          t = j;
寻找距离最小的点，这个操作可以用堆来优化。具体做法是小根堆来存储当前距离最小的点，其它步骤相同
typedef pair<int, int> PII;
int n;                            // 点的数量
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边, w[i] 是距离
int dist[N];                      // 存储所有点到1号点的距离
bool st[N];                       // 存储每个点的最短距离是否已确定

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;
				// 遍历t的所有出边
        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];
}
需要注意的是，堆里面允许冗余点存在，比如{4, 3}，{2, 3}，{7, 3}这几个组合是允许同时存在的。
st 的含义是点是否被处理过，因此只有在从堆中弹出的时候才标记 st[t] = true
时间复杂度：
适用场景：稀疏图，点多边少
一旦图中存在负权边，dijkstra 算法就失效了，只能使用 BF 算法或者 SPFA 算法求解

BF 算法

思想：
迭代 n 次，每次遍历所有边，尝试去更新dist数组。这样得到的dist数组就是最终结果了
伪代码：
for 迭代n次:
	for 所有边 a -> b, 边权 w:
		dist[b] = min(dist[b], dist[a] + w); // 松弛操作
实现：
int n, m;
int dist[N];

// 边，a表示出点，b表示入点，w表示边的权重
struct Edge
{
    int a, b, w;
} edges[M];

int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，
    // 由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if (dist[b] > dist[a] + w)
                dist[b] = dist[a] + w;
        }
    }
    if (dist[n] > 0x3f3f3f3f / 2)
        return -1;
    return dist[n];
}
时间复杂度：
适用场景：图中存在负权边

SPFA 算法

从 BF 算法中我们可以观察这个条件：
if (dist[b] > dist[a] + w)
    dist[b] = dist[a] + w;
何时才能更新 dist[b] 呢？当然是只有 dist[a] 发生变动的时候才能更新了。
SPFA 的思想也很简单，当一个点被更新的时候，才去更新它的所有出边。
这样就避免每次都遍历所有边尝试去更新最短距离了。
代码：
int n;                            // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N];                      // 存储每个点到1号点的最短距离
bool st[N];                       // 存储每个点是否在队列中

int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    queue<int> q;
    q.push(1);
    st[1] = true;
    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    if (dist[n] == 0x3f3f3f3f)
        return -1;
    return dist[n];
需要注意的地方是：st 记录的是点是否存在队列中，所以在入队的时候要标记st[j] = true ，而出队的时候要修改st[j] = false
时间复杂度：一般 ，最差
适用场景：存在负权边

负权回路

首先介绍一个概念，叫做负权回路，如下图所示
notion image
图中2，3，4组成了一个负权回路。
当负权回路处于源点和目标点的路径上时，必然无法求出最短路径。因为每经过一次负权回路，边权就-1。
对比BF算法和SPFA算法我们可以发现，上面这种情况发生的时候，BF算法迭代n次就停止，不会发生死循环，而SPFA会发生死循环。
对于这种情况，SPFA可以做一些改进，检测出是否有上面情况的存在。
int n;                            // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N], cnt[N];              // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool st[N];                       // 存储每个点是否在队列中

// 如果存在负环，则返回true，否则返回false。
bool spfa()
{
    // 不需要初始化dist数组
    // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点
    // 由抽屉原理一定有两个点相同，所以存在环。

    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        q.push(i);
        st[i] = true;
    }

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n)
                    return true; // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}
具体做法是，使用cnt数组来记录经过的点数，如果到某个点经过点数≥n，那么根据抽屉原理，此时有n+1个点，但是最多图中有n个点，所以必然存在2个点相同，因此图中存在负权回路。

对比 SPFA 和堆优化 dijkstra

堆优化 dijkstra
思想：使用小根堆来存储最小距离的点，遍历它的所有出边，尝试优化 dist
时间复杂度：O(nlogm)
核心代码：
while (heap.size())
{
		// 弹出距离最近的点，优化它的出边
    auto t = heap.top();
    heap.pop();
    int ver = t.second, distance = t.first;
    if (st[ver])
        continue;

    st[ver] = true;
		// 遍历t的所有出边
    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});  // 如果能优化，则放入点
        }
    }
}
st的作用：标记是否被处理过
SPFA
思想：使用队列来存储被更新的点，优化它的所有出边
时间复杂度：O(n)，最差O(nm)
核心代码：
while (q.size())
{
		// 弹出被更新的点
    auto t = q.front();
    q.pop();

    st[t] = false;
		// 遍历所有出边，尝试优化
    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (dist[j] > dist[t] + w[i])
        {
            dist[j] = dist[t] + w[i];
            if (!st[j])
            {
                q.push(j);
                st[j] = true;
            }
        }
    }
}
st的作用：标记是否存在队列中
可以发现上面两个版本的思想非常相似，区别仅仅在于：
堆优化dijkstra使用小根堆来保证弹出的点是目前距离最小的点，而SPFA只需要获得被更新过的点即可。
一般我们都可以用 SPFA 来解决单源最短路径问题，只有被卡的时候，才考虑堆优化版 dijkstra。

Floyd 算法

如果是要求任意两个点之间的最短路径的话，就考虑用 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;

// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
时间复杂度：O(n^3)
需要注意的是，先枚举中间点k，再枚举左右端点i和j

总结

单源最短路径：优先考虑SPFA，被卡再考虑堆优化版dijkstra
多源最短路径：Floyd

参考

AcWing 算法基础课
 

© hhmy 2019 - 2023

powered by nobelium