图论复习(最短路)

图论复习(最短路)

十二月 08, 2021

前言

​ 下学期开始讲数据结构,我自己比较想去争取一下免修。不过其实关于图论的部分基本上已经是忘得差不多了(我觉得我现在可能唯一还会的算法就是倍增求$LCA$了)。图论的部分就打算从最简单的最短路和最小生成树开始复习了(据说下学期数据结构的内容要求只有$Dijkstra$算法)。

Dijkstra

它中间的k很容易打漏

​ 应该是一个荷兰人在上世纪五十年代提出来的算法吧(记不清了),用来计算非负权图单源最短路

算法思路

​ 假设起点为$S$,$dist[i]$表示从$S$到点$i$的最短路,$vis[i]$表示是否选中了这一个点($0$表示还没有选中,$1$表示已经选中)

​ 思路如下:

  • $dist$数组初始化为$inf$,$dist[S]=0$,$vis$数组初始化为$0$
  • 重复接下来的操作$n$次(假如这个图联通的话)
    • 从没有选中的点中选择$dist$值最小的一个点$u$,$vis[u]=1$
    • 设$v$是$u$可以直接到达的节点,$val$是这两条边的权值,$dist[v]=min(dist[v],dist[u]+val)$
  • 或者说(不知道这个图到底联不联通):
    • 每次选的点加入集合,每次从集合中去出点来,直到集合为空为止

算法的正确性

​ 我就根据自己的理解给一个证明了。不保证正确性。

​ 每一次都是从没有选择的一群点中选择$dist$最小的点$u$。首先就是不可能存在路径$S \rightarrow mid\rightarrow u $,$mid$属于还没有选择的点当中,十的$dist$更小。这是因为这个图是没有负权的,其他的点$dist$都是更大的,这样转移过来$u$的$dist$不会更小了。所以说每次选的点的最短路长度都是求出来了的,所有的点选完了那么最短路就求出来了

算法的优化

​ 暴力遍历数组选择节点时间复杂度为$O(n^2)$,为了优化算法,应当考虑提高选择结点的时候的效率。

​ 考虑用优先队列进行优化,将选择节点的效率提高到$O(\log n)$,这样算法的效率就提高了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
priority_queue< pair<int,int> >Que;
void Dijsktra(){
clr(dist,0x3f);
dist[S]=0;
Que.push(make_pair(0,S));
while(Que.size()){
int u=Que.top().second;Que.pop();
if(inq[u])continue;
inq[u]=true;
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
int w=val[i];
if(dist[v]>dist[u]+w){
dist[v]=dist[u]+w;
Que.push(make_pair(-dist[v],v));
}
}
}
}

上面是一份代码的案例。有自己define的语句。

Floyd

相当简单直白的算法了。边的权值可以负可以正,无向有向均可,但是要没有负环。

算法思路

​ 点$u$到点$v$的路径可以分分解为点$u$到点$mid$再到点$v$两条路径长度之和,所以说对于任意两个点之间的最短路,都枚举一下两个点之间转移的中间节点是多少就好了。

1
2
3
4
for(int k=1;k<=N;k++)//枚举中间节点
for(int i=1;i<=N;i++)//枚举起点
for(int j=1;j<=N;j++)//枚举终点
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);

​ 缺点就是比较慢,时间复杂度达到了$O(n^3)$,优点是求得多源点最短路。

Bellman-Ford

相比于$Dijkstra$,可以处理有负边权的情况

算法思路

假设$dist[i]$表示从$S$到点$i$的最短路,$edge$是边的结构体,其中包含两个点和对应的权值

  • $dist$数组初始化为$inf$,$dist[S]=0$
  • 下面操作(松弛操作)重复$n-1$次:
    • 枚举每一条边,$dist[edge[k].u]=min(dist[edge[k].u],dist[edge[k].v]+edge[k].val)$
  • 再进行一次松弛操作,如果说松弛操作可以成功,那么就说明这个图存在负环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool Bellman_ford(){
memset(dist,0x3f,sizeof(dist));
dist[S]=0;
for(int i=1;i<N;i++){
for(int j=1;j<=E;j++){
int u=edge[j].u;
int v=edge[j].v;
int w=edge[j].w;
dist[u]=min(dist[u],dist[v]+w);
}
}
for(int i=1;i<=E;i++){
int u=edge[j].u;
int v=edge[j].v;
int w=edge[j].w;
if(dist[u]>dist[u]+dist[v]+w)return false;
}
return true;
}

算法的正确性

​ 图的最短路不会包含正权的环(假设说有正环,那么肯定是有一条边可以删掉的,建议自己画图理解一下),也不会有负环(有负环哪来的最短路)。所以说一个图的最短路最多会有$N-1$条边。

​ $N$个点,$N-1$条边,其实就是一棵树,$Bellman-Ford$可以看作是以$S$作为根,一层一层地生成这棵最短路的树的一个过程,这棵树最多有$N-1$层,所以说最多只需要进行$N-1$次操作就好了,如果说还能继续的话就说明是存在负环了。

SPFA

算法思想

​ 相当于是通过队列的方式对$Bellman-Ford$进行优化。通过队列的方式减少了多余的扫描

  • $dist$初始化为无穷大,$inq$初始化为0(用来记录是否在队列里面),$dist[S]$设为$0$,$inq[S]=1$并且放入队列当中
  • 只要队列不为空:
    • 拿出队首的元素$u$,扫描队首元素可以到达的节点$v$
    • 如果说$dist[v]>dist[u]+w$,更改值,检查$v$是否在队列当中,如果说不在队列里面的话,那么放入队列里面,$inq$设置为$1$
    • 如果说一个点加入队列的次数超过了$N$说明有负环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void SPFA(){
//没有对于负环的检测
memset(dist,0x3f,sizeof(dist));
memset(inq,0,sizeof(inq));
dist[S]=0;
inq[S]=1;
Que.push(S);
while(Que.size()){
int u=Que.front();Que.pop();
inq[u]=0;
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
int w=val[i];
if(dist[u]>dist[v]+w){
dist[u]=dist[v]+w;
if(!inq[v]){Que.push(v);inq[v]=1;}
}
}
}
}