最短路算法详解

最短路

图论基础知识——有向图、无向图

有向图：

• 即单向边，i->j有边不一定满足j->i有边

无向图：

• 即双向边，i->j有边一定满足j->i有边

主要是根据题目要求来建单向边还是双向边

如果是双向边，我们只需要把他拆成i->j和j->i的两条单向边就行

无论是单向边还是双向边，对我们最短路都没有什么影响，学会算法以后直接套就行

图论基础知识——建图

邻接矩阵建图法：

• 开一个int型的二维数组tr[i][j]，用来表示i到j之间的距离

优点：

• 无脑存图，可以O(1)判断i和j之间是否有边

缺点：

• 空间：开一个tr[n][n]的数组的开销很大，需要根据题目给的空间范围来判断是否可行
• 时间：对于一个点i，我们去遍历与它相邻的所有的点的时候，需要O(n)去枚举每个位置，看tr[i][j]是否有值，这样n个点就是 $O(n^2)$，时间开销很大

代码：

#define MAX 1050
int tr[MAX][MAX];

for(int i = 1; i <= n; ++i){//枚举i
  	for(int j = 1; j <= n; ++j){//枚举每个点j，判断是否和i相连
      	if(tr[i][j]){
          	
        }
    }
}
1
2
3
4
5
6
7
8
9
10

链式前向星

思想：

• 由于我们只想知道与u相连的点的信息，其他的我们并不在乎，所以链式前向星的本质是用数组模拟了n个单链表，每个单链表都维护的是起点为i的边的信息
• 我们需要开一个int数组head，head[i]表示i点的单链表的头
• 搞一个结构体记录每条边的信息，假设当前边是u->v，权值为c
  • 显然这条边的信息有三个：u v c
  • 由于我们head[u]的单链表维护的是所有与u相连的边，所以head[u]其实就已经记录了u的信息了
  • 我们搞一个int型的变量to，我们令to = v，即to记录的是v的信息
  • 再搞一个int型的变量c，记录的是边的权值c
  • 再搞一个int型的变量nex，指向上一条起点为u的边的id，用于进行节点的跳转，即维护单链表

优点：

• 数组模拟，常数小

缺点：

• 没什么缺点，硬要说有缺点的话，多组输入的时候，有些变量的初始化可能会忘记，比如tot

//建图
int tot;
int head[MAX];
struct ran{
    int to, nex, val;
}tr[MAX];
inline void add(int u, int v, int c){
    tr[++tot].to = v;
    tr[tot].val = c;
    tr[tot].nex = head[u];
    head[u] = tot;
}
1
2
3
4
5
6
7
8
9
10
11
12

//初始化
tot = 0;
memset(head, 0, sizeof(head));
1
2
3

for(int u = 1; u <= n; ++u){
 		for(int i = head[u]; i; i = tr[i].nex){//遍历与u相连的所有点
     		int v = tr[i].to;
      	int c = tr[i].val;
      	//u->v,c
    }
}
1
2
3
4
5
6
7

vector模拟邻接表

思想：

• 跟链式前向星的思想差不多，都是对每个i都搞一个单链表，维护的是所有起点为i的边的信息
• 不过我们可以直接用vector来维护就行，不需要数组模拟
• 我们开一个vector>G[MAX]，即开一个存pair类型的vector数组，对于一条边(u,v,c),我们只需要往G[u]里push一个(v,c)的pair就行

优点：

• 写起来比链式前向星方便很多

缺点：

• vector常数大，可能会被卡

//建图
#define m_p(a,b) make_pair(a, b)
typedef pair <int,int> pii;

#define MAX 100050
vector<pii>G[MAX];

for(int i = 1; i <= m; ++i){
  	cin >> x >> y >> z;
  	G[x].push_back(m_p(y, z));
//  G[y].push_back(m_p(x, z));
}
for(int u = 1; u <= n; ++u){
  	for(auto [v, d] : G[u]){
				
  	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

单源最短路

Q:什么是单源最短路？

A: 即处理起点 s 已知，求从s出发到其他任意点的最短距离

一些没人提，但是人尽皆知的东西

点的数量：n,边的数量：m

源点、起点：s，终点：t

最短路数组dis[i]，表示从起点s到i点的最短距离

标记数组vis[i]，不同算法的标记数组的意义不同

(u,v,c)表示u到v有一条长度为c的边

迪杰斯特拉算法

该算法的特点是从起点开始，采用贪心算法的策略，采用加点的的方式，每次遍历到与起始点距离最近且从未被访问过的顶点的邻接节点t，将该点t加入集合B中，直到扩展到终点位置。

算法步骤：

1. 我们维护两个集合，一个代表已经确定最短路的集合A,另一个就是还没确定最短路的集合B，这个可以用vis[i]来表示，vis[i]=1是A, vis[i]=0是B
2. 我们每次都从集合B中找到距离起点s最近的点，计作u点，把他放到A集合中，此时的dis[i]就是s到i的最短路的长度
3. 我们用u点，去遍历u点所有的邻边(u,v,c)，如果dis[v]>dis[u]+c,则更新一下dis[v]的值
4. 重复上述两个操作，直到所有点被标记了，结束算法

算法本质：

从步骤2可以看出，迪杰斯特拉算法的本质是贪心，每一步都是取未确定的点中距离最小的点，然后去更新其他点。这样就可以保证到目前为止，每个点的最短距离一定是由已经确定最短路的点决定的

即我们假设s到i的最短路的路径是s->a->b->c->i，当i的最短路确定的之前，在s到i的路径中的每个点的最短路一定是在这之前就确定的了

样例模拟：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nJbepVrp-1668158087918)(https://cdn.jsdelivr.net/gh/Chelseatr/image@main/uPic/IMG_6485C6692F5B-1.jpeg)]

代码实现：

int n, m, k, x;
int tot;
int head[MAX];
struct ran{
    int to, nex, val;
}tr[MAX];
inline void add(int u, int v, int c){
    tr[++tot].to = v;
    tr[tot].val = c;
    tr[tot].nex = head[u];
    head[u] = tot;
}
int dis[MAX];
bool vis[MAX];
void dijkstra(int s){
    memset(dis, inf, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    for(int i = 1; i <= n; ++i){//进行n次循环
        int id = -1, minx = inf;
        for(int j = 1; j <= n; ++j){//找当前B集合中最短路最小的点
            if(vis[j] == 0 && dis[j] < minx){
                minx = dis[j];
                id = j;
            }
        }
        vis[id] = 1;
        for(int i = head[id]; i; i = tr[i].nex){
            int v = tr[i].to;
            if(dis[v] > dis[id] + tr[i].val){
                dis[v] = dis[id] + tr[i].val;
            }
        }
    }
    for(int i = 1; i <= n; ++i)cout << dis[i] << ' ';
}
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

分析时间复杂度：

$O(n^2)$

STL之pair

• 定义方式：paira,p,q可以是任意类型的变量

• 比较常用的是：p=q=int，此时pair等同于:

  struct node{
    	int x, y;
  };
  1
  2
  3

• 定义方式：paira

• 访问方式：a.first和a.second

• 产生一个pair类型的变量的方法是：make_pair(x, y)

STL之优先队列

普通队列是先进先出，优先队列是优先级高的元素先出队列，并非按照先进先出的要求

什么样的元素的优先级高？这个可以由我们自己决定

默认版本的优先队列是priority_queue，队列的元素是一个int型的，队顶是最大的元素，俗称大根堆

如果想要最小的元素放在堆顶，则写成priority_queue,greater>q，俗称小根堆

如果想塞结构体什么的，就得自己重载运算符，这里就不展开了，想知道的可以自己去学一学

如果优先队列塞的是pair，会根据pair的排序方法来确定，pair应该是先第一位，在第二位

优先队列优化dijkstra

简单分析一下，我们的第一层循环是不能优化掉的，因为每次只能确定一个点的最短路，所以要进行n次，但是第二层循环，我们做的是找出一个集合中dis最小的点，然后去更新与他相邻的所有的点

所以我们其实可以用一个容器去快速地去维护最小的dis[i]的i

即我们优先队列需要放两个元素，一个是dis[i]，另一个是i，我们取dis[i]最小的那个，所以想要的是小根堆

用pair的小根堆，定义方式如下：

priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > >q;
1

q.top()就是堆顶的元素，是pair类型，是(dis[i], i)

其实也可以用大根堆priority_queue >q ，由于pair第一维度最小，所以我们只需要塞(-dis[i], i)

结构体作为优先队列的元素也是可以的

#define m_p(a,b) make_pair(a, b)
typedef pair <int,int> pii;

int tot;
int head[MAX];
struct ran{
    int to, nex, val;
}tr[MAX];
void add(int u, int v, int c){
    tr[++tot].to = v;
    tr[tot].val = c;
    tr[tot].nex = head[u];
    head[u] = tot;
}
int dis[MAX];
bool vis[MAX];
void dijkstra(int s){
    priority_queue<pii, vector<pii>, greater<pii>>q;
    mem(dis, 0x3f);
    q.push(m_p(0, s));
    dis[s] = 0;
    while (!q.empty()) {
        int u = q.top().second;q.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(int i = head[u]; i; i = tr[i].nex){
            int v = tr[i].to;
            if(dis[v] > dis[u] + tr[i].val){
                dis[v] = dis[u] + tr[i].val;
                q.push(m_p(dis[v], v));
            }
        }
    }
}
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

思考：

迪杰斯特拉的贪心算法真的正确吗？

给个例子：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-v258EHhD-1668158087919)(https://cdn.jsdelivr.net/gh/Chelseatr/image@main/uPic/image-20221111091902915.png)]

迪杰斯特拉的贪心策略是，每次都找一个距源点最近的点，然后将该距离定为这个点到源点的最短路径；但如果存在负权边，那么直接得到的最短路不一定是最短路径，因为可能先通过并不是距源点最近的一个次优点，再通过一个负权边，使得路径之和更小，这样就出现了错误。

迪杰斯特拉总结

• 只能处理正权边
• 朴素版时间复杂度： $O(n^2)$, 优先队列优化后时间复杂度: $O(mlogm)$

板子题：

P4779 【模板】单源最短路径（标准版）

Bellman-Ford 算法

Bellman-Ford 算法是求含负权图的单源最短路径的一种算法，效率较低，代码难度较小。

算法操作：

迭代n次，每次都遍历所有边(u, v, c),去更新dis[v] = min(dis[v], dis[u] + c)

算法思想：

其原理为连续进行松弛，在每次松弛时把每条边都更新一下，最多进行n-1次松弛操作

为什么是n-1?

因为一共n个点，从起点到终点的简单路径中最多有n-1条边

所以如果在 n-1 次松弛后还能更新，则说明图中有负环。

缺点：

• 极其暴力，复杂度:O(nm)

SPFA

对Bellman-Ford 算法的优化

每次迭代的时候不是所有边都能进行有效的更新

只有当dis[v]>dis[u]+c的时候才有更新的必要

也就是只有dis[u]变小了，(u, v, c)的边才有意思

所以我们可以搞一个队列存下来所有dis变小的节点u

只要我们队列不为空，即还存在变小的dis[u]没去更新，我们就需要去更新

更新的时候，如果dis[v] > dis[u]+c,则说明dis[v]变小了，我们就放进队列里面，但是如果有些点已经在队列里面了，我们就不需要把他放进去，所以搞一个vis[i]数组进行标记，如果在队列里就赋1，否则是0

int tot;
int head[MAX];
struct ran{
    int to, nex, val;
}tr[MAX];
inline void add(int u, int v, int c){
    tr[++tot].to = v;
    tr[tot].val = c;
    tr[tot].nex = head[u];
    head[u] = tot;
}

bool vis[MAX];
int dis[MAX];
void SPFA(){
    queue<int>q;
    mem(dis, inf);
    q.push(1);dis[1] = 0;
    while (!q.empty()) {
        int u = q.front();q.pop();vis[u] = 0;
        for(int i = head[u]; i; i = tr[i].nex){
            int v = tr[i].to;
            if(dis[v] > dis[u] + 1){
                dis[v] = dis[u] + 1;
                if(!vis[v]){
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
}
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

不过SPFA很容易被网格图卡成O(n*m)，有很多玄学优化的方式，但是出题人要是想卡，每种方式都能卡掉

板子题：

P3371 【模板】单源最短路径（弱化版）

多源最短路-Floyed

多源最短路问题一般是求任意两点间的最短路径

在学会单源最短路的情况下，我们其实可以跑n次单源最短路求出多源最短路，复杂度是O(nmlogm)

在n很小，m很大的情况下，就不适合了

我们可以用Floyed算法来求解

Floyed算法思想：

Floyed本质是动态规划

我们用dis[k][i][j]表示i到j经过若干个编号不超过k的节点的最短路径的长度

那要求dis[k][i][j]这个状态的答案，我们可以考虑将其分成两个子状态：

• i到j的最短路中不包含k点，则dis[k][i][j] = dis[k-1][i][j]
• i到j的最短路中包含k点，则dis[k][i][j] = dis[k-1][i][k] + dis[k-1][k][j]

则状态转移方程式是：

dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k]+dp[k-1][k][j])

复杂度：

时间复杂度 $O(n^3)$

空间复杂度也是 $O(n^3)$

优化：

可以发现计算第k层的时候只用到了第k-1层，所以可以省略掉这一维度，直接写成dp[k][i][j] = min(dp[i][j], dp[i][k]+dp[k][j]),减少空间的浪费

初始化：

由于是dp问题，我们必须解决初始化的问题：如果i->j存在长度为c的边，则dp[i][j] = c,其他的我们就赋个1e9，表示没有边

for(int k = 1; k <= n; ++k){
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= n; ++j){
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
1
2
3
4
5
6
7