【图论】最短路

【图论】最短路

EveSunMaple Lv3
  2023-05-14 00:05 2023-05-14 00:05 创建   2024-02-23 12:02:20 2024-02-23 12:02:20 更新      3.8k 字  15 分钟  

前言

最短路是图论最重要的算法之一，也是算法难点。经过这篇的学习，你会发现你离成功就差一个最短路的距离（虽然它难以被找到）。最短路是指，某个点到某个点之间的距离最短的路径。

必要的知识

学会存储一张有向图，我们一般使用邻接矩阵和邻接表。因为邻接矩阵的储存方式有时无法满足题目规定的空间复杂度限制，为此这里我们只使用邻接表储存有向图。储存无向图可以看成是两条相反方向的有向边

关于邻接表的存图方式，请浏览【数据结构】邻接表与链式前向星 。

2023/6/16修正：
此存图方式应为链式前向星，邻接表使用vector而非数组模拟链表，详见上方链接

最短路算法

一、Dijkstra算法

1.算法基本介绍

Dijkstra算法通常是求解单源最短路中最快的算法，但它无法处理存在负权边的情况（原因在正确性证明中）。Dijkstra本质上是一种贪心算法，通过不断调整每个点的“当前距离”最终得到最优结果，其实后面要讲到的几种算法也大都是采用这种步步逼近的手段。这种不断调整的过程，维基百科上面称为“relax”。以上可能有点抽象，下面是算法的流程。

2.算法流程

假设现在要求出从某一点s到其他所有点的最短距离，对于每个点v均维护一个“当前距离”（dist[v]dist[v]）和“是否访问过”(visited[v]visited[v])。首先将dist[s]dist[s]初始化为0，将其他点的距离初始化为无穷，并将所有点初始化为未访问的。记u−>vu->v的边权为weight[u−>v]weight[u->v]（程序中我们使用edge数组存储，下标为u−>vu->v这条边的序号，详见邻接表一栏）。然后进行以下步骤：

  1. 从所有未访问的点中，找出当前距离最小的，设为u，并将其标记为已访问的。
  2. 调整u的所有边（若是有向图则为出边）连接的并且未被访问过的点：若weight[u−>v]+dist[u]<dist[v]weight[u->v] + dist[u] < dist[v], 则将dist[v]dist[v]更新为dist[u]+weight[u−>v]dist[u]+weight[u->v]。
  3. 重复1和2步骤，直到所有点都被标记为已访问的，则dist[i]dist[i]即s到i的最短距离。如果只想求从s到某一点的最短距离，那么当该点被标记为访问过之后可直接退出。
  4. 补充：如果除了最短距离之外还想求出具体的路径，只需建立一个prepre数组，在步骤2后添加操作：pre[v]=upre[v] = u（前提是dist[v]dist[v]被更新）。类似于邻接表中son数组的链式结构。

3.正确性证明

我们证明，当某个点v被标记为已访问后，s到其的最短距离即为dist[v]dist[v]，即在步骤1中选出的每个点的当前距离即为最短距离。

首先容易理解，如果从s到v的路径只允许经过已访问过的点，那么dist[v]dist[v]是这些路径中最短的。倘若存在一条包含未访问过点（除v之外）的更短的路径，设这条路径上第一个未被访问过的点为m，则显然有dist[m]<dist[v]dist[m] < dist[v]（注意因为m是这条路径上第一个未被访问的点，所以沿着这条路径走到m的距离一定为dist[m]dist[m]）。而这与v的选取方式——从所有未访问过点中选取当前距离最小的相矛盾。

解释一下Dijkstra算法为什么不能用于有负权的边的图：

text4.png
text4.png

因为Dijkstra算法是通过当前离起点最近的点来更新其他的点的距离，例如上图中的 4 号结点会被 2 号结点更新为2+3=5，但实际上4号结点的最短路径是4+(-4)=0!，这样你就知道为什么Dijkstra算法不能用于有负权的边的图吧。

4.代码实现

这里使用邻接表储存有向图，关于邻接矩阵的算法读者可以自己上网查询。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <algorithm>
#include <cstring>
#include <cmath>
#define MAX 10000
int head[MAX]; //代表一个结点，也是子结点链的起点
int edge[MAX]; //储存边的值
int son[MAX]; //子结点链
int ver[MAX]; //代表有向边
int dist[MAX]; //最短路
bool tag[MAX]; //标记结点
int tot = 0; // 边的数量
using namespace std;
void Dijkstra()
{
    memset(dist, 0x3f, sizeof(dist)); //初始化dist
    memset(tag, 0, sizeof(tag)); //初始化tag
    dist[1] = 0; //设置起点
    //计算除终点以外的结点出发的子结点的最短路
    for(int i = 1; i < N; i++)
    {
        int crd = 0; //父结点下标
        //遍历N个结点，找到dist最小的结点
        for(int j = 1; j <= N; j++)
        {
            if(!tag[j] && (crd == 0 || dist[crd] > dist[j]))
            {
                crd = j;
            }
        }
        tag[crd] = true; //标记已经走过的点
        //遍历此结点的子结点
        for(int j = head[crd]; j; j = son[j])
        {
            int ne = ver[j];
            dist[ne] = min(dist[ne], dist[crd] + edge[j]); //更新子结点的dist
        }
    }
    return;
}

堆优化Dijkstra：

我们使用小根堆对dist数组进行维护，每次只扩展有可能改变的结点，我们只需要O(logN)O(log N)的时间即可维护一个二叉堆，而找到最小distdist结点只需要O(1)O(1)。

关于小根堆的实现方法读者可自行查询，这里我们直接存储负值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
#define MAX 10000
int head[MAX]; //代表一个结点，也是子结点链的起点
int edge[MAX]; //储存边的值
int son[MAX]; //子结点链
int ver[MAX]; //代表有向边
int dist[MAX]; //最短路
bool tag[MAX]; //标记结点
int tot = 0; // 边的数量
using namespace std;
//pair的第一维是dist的相反数（把大根堆转换成小根堆）
//pair的第二维是结点下标
priority_queue<pair<int int>> q; //用二叉堆存结点
void Dijkstra()
{
    memset(dist, 0x3f, sizeof(dist)); //初始化dist
    memset(tag, 0, sizeof(tag)); //初始化tag
    dist[1] = 0; //设置起点
    q.push(make_pair(0, 1)); //把起点加入二叉堆
    //一直计算直到队列为空
    while(q.size())
    {
        int crd = q.top().second; //父结点下标
        q.pop(); //移出二叉堆
        if(tag[crd]) continue; //确保此结点没有被扩展过
        tag[crd] = true; //标记已经走过的点
        //遍历此结点的子结点
        for(int j = head[crd]; j; j = son[j])
        {
            if(dist[crd] + edge[j] < dist[ne])
            {
                 dist[ne] = dist[crd] + edge[j]; //更新子结点的dist
                 q.push(make_pair(-dist[ne], ne)); //把新的二元组插入堆
            }
        }
    }
    return;
}

二、Bellmon-Ford 算法和 SPFA

首先介绍bellmon-ford算法，SPFA（shortest path faster algorithm)是对它的一个改进。

bellmon-ford是一种单源最短路算法，时间复杂度是 O(VE)O(VE)，显然不如Dijkstra快，但它可以处理负权边和负权环的情况。它基于一个很基本的事实： 对于一个不包含负权环的V个点的图，任意两点之间的最短路径至多包含V−1V-1条边。 如果存在负权环，每次在负权环上走一圈都会使环上的每一个点的距离减少 （如果计算时步数超过了V−1V-1，说明有负权环），因此不存在最短路径。bellmon-ford算法可以检测出这种情况。

算法的实现也很简单，根据三角形不等式，对于图中的某一条边(u,v,t)(u,v,t),有dist[v]<=dist[u]+tdist[v] <= dist[u] + t成立，就说它满足三角形不等式，可以发现，此不等式就是这一条边在有限范围内的最优解。通过重复扫描边，直到所有边都符合三角不等式，此时dist数组就是结果（是不是很暴力很简单）。

正因为它不像Dijkstra这么贪心，不会漏过负权边，所以它可以正确处理有负权边的图的最短路问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <algorithm>
#include <cstring>
#include <cmath>
#define MAX 10000
int edge[MAX]; //储存边的值
int ver[MAX]; //代表有向边出发的结点
int son[MAX]; //代表有向边指向的结点
/*
注意这里ver和son的含义改变了
ver存的是一条边的起点下标
son存的是一条边的终点下标
请读者自己更改添加边函数
*/
int dist[MAX]; //最短路
int tot = 0; // 边的数量
using namespace std;
void BellmonFord()
{
    memset(dist, 0x3f, sizeof(dist)); //初始化dist
    dist[1] = 0; //设置起点
    //循环N – 1次，因为无负环的最短路步数最多为N – 1
    for(int i = 1; i < N; i++)
    {
        //遍历tot条边，找到指向结点dist最小的边
        for(int j = 1; j <= tot; j++)
        {
            if(dist[ver[j]] + edge[j] < dist[son[j]])
            {
                dist[son[j]] = dist[ver[j]] + edge[j];
            }
        }
    }
    return;
}

此版本的Bellmon-Ford算法不需要邻接表，但SPFA仍然要使用邻接表，望读者一定要熟悉邻接表的使用方法，不要被暴力迷了双眼

算法中，dist[i]dist[i]为源点到i的当前最短距离。算法最外层是一个N–1N – 1次的循环，在每次循环中，算法遍历所有的边并执行操作。

bellmon-ford算法不断对每条边进行所谓的松弛（relax）操作，如果u到v有一条边，那么dist[u]dist[u]减小意味着dist[v]dist[v]可能也可以进行更新，然而由于不知道到底哪些点的当前距离需要更新，bellmon-ford算法选择暴力地去遍历每条边来检查哪些点的当前距离可以更新 （这也是我们要优化的地方）。

如果在某次外层循环中发现所有点的当前距离都没有被更新，那么可以直接停止算法，因为接下来无论再进行多少次循环点的距离也不会被继续更新了。

bellmon-ford算法可以判断负权环的存在：只需在算法的最后对每条边再松弛一次，如果发现有点的距离得到更新 （说明经过N–1N – 1次循环仍然有边不满足三角形不等式，而只有负环会出现这种情况，因为负环永远不可能满足三角形不等式），说明存在负权环——因为没有负权环时最短路径的长度至多为N–1N – 1。

SPFA：

从上面的介绍我们知道bellmon-ford算法是带着一定的盲目性的，因为三角形不等式是这一条边在有限范围内的最优解，很多时候（比如刚开始赋值无限大）根本不存在最优解，白白浪费了时间。作为对它的优化，SPFA采用类似BFS的思想，使用一个队列，只松弛那些可能更新点的距离的边，也就是那些已经被改变，不再是无限大（也可能再次被改变），可能对下一个结点有影响的结点队列。算法的流程为：

  1. 将除源点之外的所有的点当前距离初始化为无穷，并标记为未入队。源点的当前距离为0，将源点入队。
  2. 取出队首u，遍历u的所有出边，检查是否能更新所连接的点v的当前距离。如果v的当前距离被更新并且v不在队中，则将v入队。重复该操作直到队列为空。
  3. 检查是否存在负权环的方法为：记录一个点的入队次数，如果超过N–1N – 1次说明存在负权环，因为最短路径上除自身外至多N–1N – 1个点，故一个点不可能被更新超过N–1N – 1次。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
#define MAX 10000
int head[MAX]; //代表一个结点，也是子结点链的起点
int edge[MAX]; //储存边的值
int son[MAX]; //子结点链
int ver[MAX]; //代表有向边
int dist[MAX]; //最短路
bool tag[MAX]; //标记结点
int tot = 0; //边的数量
int N;
using namespace std;
void BellmonFord()
{
    memset(dist, 0x3f, sizeof(dist)); //初始化dist
    dist[1] = 0; //设置起点
    queue<int> q; //定义队列，存储可能改变的结点
    q.push(1); //把起点添加进队列
    tag[1] = true; //打上标记
    while (!q.empty()) //一直循环，直到队列为空
    {
        int crd = q.front(); //从队列中取一个结点
        q.pop(); //移出队列
        tag[crd] = false; //去掉标记
        //遍历连接crd的子节点
        for(int j = head[crd]; j; j = son[j])
        {
            int ne = ver[j];
            if(dist[crd] + edge[j] < dist[ne])
            {
                dist[ne] = dist[crd] + edge[j];
                if(!tag[ne]) //如果子节点并不在队列中
                {
                    q.push(ne); //加入队列
                    tag[ne] = true; //打上标记
                }
            }
        }
    }
    return;
}

三、Floyd算法

Floyd算法又称为Floyd-Warshell算法，其实Warshell算法是离散数学中求传递闭包的算法，两者的思想是一致的。Floyd算法是求解多源最短路时通常选用的算法，经过一次算法即可求出任意两点之间的最短距离，并且可以处理有负权边的情况（但无法处理负权环）。

原理：

Floyd本质上是动态规划的思想。倘若现在我们想求i到j的最短路径长度，我们限制这条路径上除i和j之外只准经过前k个点（这样的路径称为k允许路径），我们在算法的最外层循环每次将k加1，那么当k等于点数时求得的结果便是最优的。下面用数学归纳法证明算法的正确性：

即证明在第n次循环后dist[i][j]为i到j的最短n允许路径，当n=0时，i到j不准经过任何点，dist[i][j]即为weight[i->j]或者无穷大，显然成立。

假设n=k时成立，那么当n=k+1时，倘若i到j的最短k+1允许路径不经过第k+1个点，则dist[i][j]不发生改变。若i到j的最短k+1允许路径经过第k+1个点，由归纳假设，此时dist[i][k+1]为i到k+1的最短k允许路径，dist[k+1][j]为k+1到j的最短k允许路径，故i到j的最短k+1允许路径长为dist[i][k+1] + dist[k+1][j]。这正是算法中的状态转移方程。

算法的实现非常简单，是一个三重循环：

1
2
3
4
5
6
7
8
9
10
11
int dist[100][100]; //初始化dist数组
for (int k = 0; k < v; k++)
{
    for (int i = 0; i < v; i++)
    {
        for (int j = 0; j < v; j++)
        {
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        }
    }
}
  • 标题: 【图论】最短路
  • 作者: EveSunMaple
  • 创建于 : 2023-05-14 00:05:00
  • 更新于 : 2024-02-23 12:02:20
  • 链接: https://old.saroprock.com/post/1824baaa.html
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
推荐阅读
【搜索】优先队列BFS 【搜索】优先队列BFS 【数据结构】邻接表与链式前向星 【数据结构】邻接表与链式前向星 【图论】强连通分量 【图论】强连通分量
推荐阅读
【搜索】优先队列BFS 【搜索】优先队列BFS 【数据结构】邻接表与链式前向星 【数据结构】邻接表与链式前向星
 评论
此页目录
【图论】最短路
  1. 1. 前言
  2. 2. 必要的知识
  3. 3. 最短路算法
    1. 3.1. 一、Dijkstra算法
    2. 3.2. 二、Bellmon-Ford 算法和 SPFA
    3. 3.3. 三、Floyd算法