「算进」[图论]最短路

图论是信息竞赛的一个极其重要的专题,那么,就先从图论里面最简单的最短路开始讲起。
对于一张有向图,我们一般采用的是邻接矩阵和邻接表两种储存路径的方式。对于一张无向图,我们可以把无向边看作两条方向相反的有向边,然后我们就可以把有向边和无向边加在一起储存了。
所以对于我们讨论图的最短路问题时,我们都以有向图为例设图G=(V,E)V是点集,E是边集。(x,y)代表从xy有一条边,他的边权为w(x,y),设n=|V|,m=|E|,邻接矩阵的大小为n^2
那么我们矩阵的时空复杂度为O(n^2)
假如我们用邻接表代码时,我们每一个点只记录一个边,每个边之后再记录一个边,就是类似HASH里面的链表一样。
那么邻接表的复杂度就会比邻接矩阵少的多,一般为O(n+m)
最短路有很多种算法如单多源最短路等。
那么就一个一个分析一下各种最短路的区别。

单源最短路

Dijkstra

Dijkstra可以很好的解决再稠密图中的单源最短路的。
主要算法流程是
1. 先把st源点的d值设成0,其他为无穷大
2. 然后由源点向外扫描找到其他的点,并更新其d值为目前最短路径,并且标记该节点
3. 把扫描过的点的d值压入小根堆,然后取出来代替st继续重复1的操作,直到全部节点已经被标记过。
用Dij这种类似贪心的方法可以很快求出源点到每个节点的最短路径的长度。
Dij在稠密图上运行效率较高,时间复杂度为O(n^2),而且Dij不可以在有负权路径的图上搜索。

SPFA算法

SPFA是现在信息竞赛里面很常用的一个求最短路的算法,那么怎么做呢,我们以目前较为常用的版本来讲把。
1. 建立邻接表,其实我喜欢叫边目录
2. 把st压进队列里面,先把st源点的d值设成0,其他为无穷大
3. 从队列头取一个点并踢出队列,然后根据边目录向外拓展,更新别的点的值,并且把别的点压进队列,这里还可以特判一下看看队列里面有没有重复的,又重复的就不压进去。
4. 重复第2步直到队列里面没有元素。
这就是目前SPFA算法的主要流程,其实SPFA就是旧的Bellman-Ford算法的队列升级版。
SPFA在稀疏图上的运行效率极高经常可以达到O(nk)k是一个很小的常数代表平均入队列的次数。但是SPFA在稠密图上面可能退化成O(nm),SPFA可以在有负权路径的图上搜索,但是也要加特判,如果一个点进入队列超过n次就是遇到了负权回路,退出就好。

Telephone Lines

简化一下题意,这题是在无向图上求出一条从1N的路径,使路径上第K+1大的边权尽量小。
这样的话我们可以发掘这题的金额是有二分性的,在合法的金额里面一定包含着最优金额,这样子我们就可以二分出最优金额进行求解,跑一下SPFA,金额大于mid的边边权为1,其他为0,最后判断一下d[ed]是否大于k就好,大于就是代表我现在金额不能完全修完前k条路径,然这题就解决了
AcceptCode

最优贸易

这题主要是求一条路径上顺序的两个点的差的最大值,题目给出的边可能是单向边,也可能是双向边,对于求单一路径上最大值和最小值还是很好求的嘛,BFS一下我们就很好的求出这个答案了=v=。
但是怎么求两个顺序的点呢?
那么我们分解一下问题。
我们枚举每一个点,我们可以求出源点到这个点的最小价值路径,那么我们只需要看看有没有一条最大路径连到终点就好。
我们还可以重新连一次反向图,倒过来建边,然后从终点跑一次维护到每一个点的最大值,最后枚举每个点,最大最小值减一减就好。
AcceptCode

两个点之间的最短路径

Floyd算法

Floyd我们经常就直接叫做弗洛伊德算法,弗洛伊德算法的特点就是时间特别大,可以渠道O(n^3)但是他有别的搜索算法比不上的好处就是可以求任意两个点之间的最短路径。因为在求任意两点之间的最短路径的题目里面,图一般比较稠密,所以还是使用弗洛伊德算法比较好,毕竟SPFA会退化的呢。
Floyd算法的思维其实就是动态规划,这个不细说,我们就说说我们现在的做法。
我们用一个数组d[i][j]表示从第i个点到第j个点的最短路径。我们有三个变量k,i,j这个顺序是不能变的呢。我们通过k枚举一个中继点更新一下d[i][j]的最短距离。怎么理解呢?就是我们判断一下从i->k再从k->j的距离是否小于i->j是的话就更新一下。
所以方程就为d[i][j]=min(d[i][j],d[i][k]+d[k][j])
这样求两个点之间的最短路径就可以直接输出d[i][j]就好了。
这样也叫做弗洛伊德里面的传递闭包

Sorting It All Out

这题的话呢,我们可以把A \lt B想象成一条从AB的边,可以互相到达,d[i][j]=true表示A可以到达B,这样呢,把所有边处理一下跑一下Floyd,我们就可以知道点的关系了,对于所有点,如果有d[i][j]=d[j][i]=false那么不够条件判断,如果有d[i][j]=d[j][i]=true那么就代表有东西重复了,矛盾了。如果没有以上两种情况,则代表是有序了的。
那么我们后面可以通过二分求出X的值,只要二分个mid重新建一个边,然后再判断一下,就好了呢。
代码放弃先,没写二分

发表评论

电子邮件地址不会被公开。 必填项已用*标注