【算法-图论-最短路】最短路算法全攻略

由 联环己烷 发布

Floyd

Floyd算法是一种$O(n^3)$时间复杂度的优秀的最短路算法,其极致简约四行代码如下:

for(RI k=1;k<=n;++k)
    for(RI i=1;i<=n;++i)
        for(RI j=1;j<=n;++j)
            if(dis[i][k]+dis[k][j]<dis[i][j]) dis[i][j]=dis[i][k]+dis[k][j];

思路也不难理解,我们每次求出只能经过前$k$个点的最短路,显然有一个dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);的DP方程。

洛谷P6175:求一张无向图(边有边权)的最小环($n \leq 100$)

在Floyd的过程中,做到点$k$的同时,求出以$k$为环上最大点的最小环。若枚举与$k$相连的两条边,终点分别是$i,j$,那么最小环上$i$到$j$之间的另一条路径一定是它们之间的最短路。

poj3613:求一张图上从$S$到$T$间经过$k$条边的最短路($n \leq 100,k \leq 10^5$)。

显然,从S到T经过$k_1+k_2$条边的最短路,是由$S$到$p$经过$k_1$条边,$p$到$T$经过$k_2$条边两段构成的。所以若我们求出了图上任意一点到另一点经过$k_1$条和$k_2$条边的最短路,就可以像矩阵快速幂一样进行Floyd的结合。

Dijkstra

一种基于贪心思想的很棒的最短路

算法思路

dis[]表示某一节点当前求得的最短路值。“标记”表示改点最短路值已经确定。

  1. 起点标记,dis值为0,其他点dis值为1。
  2. 取上一个标记点,遍历与其相邻的所有边,将终点的dis与该点dis加边权比较大小并更新。
  3. 遍历所有未标记点,取其中dis值最小的点标记。
  4. 重复步骤2~3直至所有点都被标记。

复杂度:每条边在其两端点被遍历时都会访问一遍。一共做$n$次标记,每次选下一个标记点时要遍历所有点。综上,复杂度为$O(n^2)$

正确性伪证

显然,对于当前dis最小点,与其有边相连的所有标记点都已经对它进行了更新。而对于与其相连的未标记点,它们的dis都比这个点大,不可能更新这个点的dis。所以起点到该点的最短路,已经得出。

堆优化

我们寻找dis最小点用的方法是遍历,那如果能用堆来找呢?

复杂度:每次在堆中更新dis值复杂度是$\log{n}$的,每条边都会做一次更新,加上有$n$次查找堆中最小值,故复杂度为$O((m+n) \log{n})$的。

warning:在边特别多的情况下,堆优化可能比不优化要慢。

如果你使用stl priority_queue,每次更新dis时,都要将一个点插入堆中,故复杂度是$O((m+n) \log {m})$的。

这时一定有聪明的小朋友想到了,既然可以用堆优化,那么凡是可以修改和查询最小值的数据结构不都能优化吗?欢迎大家使用线段树优化,Splay优化,Treap优化……

负权边

模板题:洛谷P5905(坑题一道,SPFA部分用stack会比较快)

Dijkstra无法处理负权边。

回顾Dijkstra正确性的证明,其中有一环就是dis值大的点不能对dis值小的点进行更新,但是如果图中有负权边,这个性质就不成立了。

咋办呢?

我们首先想到的,肯定是把所有边都加同一个正值。但是,我们无法确定最短路走了几条边。

而解决方法其实很简单。我们可以让所有点有一个点权val[i],一条边(x,y)的权值加上val[x]-val[y]。求出的s到t的最短路值为:

$w_1+val_s-val_{p_1}+w_2+val_{p_1}-val_{p_2}+...+w_m+val_{p_n}-val_t$

即$w_1+w_2+...+w_m+val_s-val_t$

这个值只受s和t的影响,很容易还原回原图上的最短路值。

而对于val的要求,就是每一条边处理后都能是正的。假设对图已经跑过了一遍最短路,求出了一个dis值,则显然,对于一条边(x,y),dis[x]+w>dis[y],所以w+dis[x]-dis[y]>0,那么将dis作为val即可。

Bellman-Ford和SPFA

Bellman-Ford是一种$O(nm)$时间复杂度的算法,即进行$n$次这样的操作:查看每一条边(x,y),看dis[x]+w是否能够将dis[y]更新。显然若无负权环,最短路最多走过$n$条边,这样一定能够求出最短路。

而所谓的SPFA(Shortest Path Faster Algorithm有没有觉得这个名字特low),也是一种$O(nm)$时间复杂度的算法(划重点!!!),即Bellman-Ford的队列优化,通过将被更新过的点放入队列中(显然只有被更新过的点才有更新别的点的能力),每次取出队列中的点,枚举与其相邻的边,更新……这样的方式在随机图上能够做到很快(这也是为何,历史上曾有很多OIer都认为SPFA是一种优秀的算法),但是,它的时间复杂度上限并没有优化

另外一提:$O$打头的叫做复杂度上限,也是最常用的。

$\Omega$(读作Omega)打头的叫做复杂度下限,$\Theta$(读作Theta)打头的叫做严格复杂度上下限。大家分析时间复杂度时,不要像我一样乱用符号。

举例:网格图卡SPFA。构造一个网格图,一边很长(10000)一边很短(10),长边的那些边的边权都很大,短边的那些边权都很小。如此一来,到达各个点的最短路很可能要走短边,然而,长边处的点会一个接一个的更新,并且长边上的点被走短边上的路径更新后,这种更新的影响也会一个接一个地沿长边传递,如此一来,SPFA就会被卡到更接近上限。

代码如下(当然,真要出题的话,得搞一些随机边,还得把点的标号打乱):

#include<bits/stdc++.h>
using namespace std;
#define RI register int
const int N=10000;
int n,m;
int main()
{
    srand(time(0));
    n=N*10,m=(N-1)*10+N*9;
    printf("%d %d 1\n",n,m);
    for(RI i=1;i<=10;++i) {
        for(RI j=1;j<N;++j)
            printf("%d %d %d\n",(i-1)*N+j,(i-1)*N+j+1,rand()%N+10);
        if(i!=10) for(RI j=1;j<=N;++j) printf("%d %d %d\n",(i-1)*N+j,i*N+j,1);
    }
    return 0;
}

然而,你能不能想一些瞎搞算法,来在网格图上快速求解呢?

更多瞎搞及其HACK->

判负环

无负环的图上,起点到任意点最短路经过的点数最多为$n$,那么我们可以记录当前求出到这个点的最短路经过了几个点,如果超过了$n$,显然图有负环。

除此之外,还有dfs版SPFA,即沿着能不断更新最短路值的点走,如果走出了环,说明原图存在负环:

int spfa(int x) {
    vis[x]=1;
    for(int i=h[x];i;i=ne[i])
        if(dis[x]+w[i]<dis[to[i]]) {
        dis[to[i]]=dis[x]+w[i];
        if(vis[to[i]]||spfa(to[i])) return 1;
    }
    vis[x]=0;return 0;
}

差分约束

有$n$个未知数和$m$个形如$x_a-x_b \leq c_i$的条件($c_i$为常数),求一组$x$的整数解,使得所有条件都可以满足(或无解的话输出无解信息)

显然求最短路后有dis[a]+w[i]>=dis[b],所以只需建含边$(x_b,x_a,c_i)$的图,用SPFA求最短路,dis值即可行解。至于无解的情况,就是有负环的情况。

poj1201 有50000个灯从左到右排成一排,有$n(n \leq 50000)$个条件,每个条件形如区间$[l,r]$内要有$k$盏灯被点亮,问至少要点亮几盏灯?

差分约束做法:设s[i]为前i盏灯点亮了多少盏,则有限制条件:s[i]+1>=s[i+1],s[i]<=s[i+1],s[r]>=s[l-1]+k

树状数组做法:贪心,将区间按照右端点从小到大排序依次处理,显然最多点亮$50000$盏灯,那么就一盏一盏的点。用树状数组查询一个区间内已经点亮了多少盏灯,若点的还不够,就从区间右端点开始一盏一盏地点。

HDU1534 有$n$项工作,每项工作有一个用时。工作与工作之间有“$a$要在$b$完成后启动,$a$要在$b$启动后启动,$a$要在$b$完成后完成,$a$要在$b$启动后完成”这四种形式的条件。求一个合理的安排工作方案,所有工作完成时间尽可能地早。

将每个工作的启动时间和结束时间分别建点,剩下的还用我说嘛……


暂无评论

发表评论


京公网安备 11010802033049号