图论复习(最短路)
前言
下学期开始讲数据结构,我自己比较想去争取一下免修。不过其实关于图论的部分基本上已经是忘得差不多了(我觉得我现在可能唯一还会的算法就是倍增求$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 | priority_queue< pair<int,int> >Que; |
上面是一份代码的案例。有自己define的语句。
Floyd
相当简单直白的算法了。边的权值可以负可以正,无向有向均可,但是要没有负环。
算法思路
点$u$到点$v$的路径可以分分解为点$u$到点$mid$再到点$v$两条路径长度之和,所以说对于任意两个点之间的最短路,都枚举一下两个点之间转移的中间节点是多少就好了。
1 | for(int k=1;k<=N;k++)//枚举中间节点 |
缺点就是比较慢,时间复杂度达到了$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 | bool Bellman_ford(){ |
算法的正确性
图的最短路不会包含正权的环(假设说有正环,那么肯定是有一条边可以删掉的,建议自己画图理解一下),也不会有负环(有负环哪来的最短路)。所以说一个图的最短路最多会有$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 | void SPFA(){ |