图论的各种奇技淫巧

就是想复习一下图论…..


建图

邻接矩阵邻接表 。说白了就是一个存每两个点中的关系,另一个就是储存边。

深入 $OI$ 这么久了,除了要用 $Floyd$ 的地方,其他基本上都用邻接表了,不多说。

最短路

$Floyd$

很暴力的三重循环,多源最短路,本质是 $dp$ 。

有一点比较重要的是,$Floyd$ 有的时候会和矩阵快速幂结合在一起。

如题:[SCOI2009]迷路

$Dijkstra$

也不多说,每次选择最近的一个点进行松弛操作,朴素复杂度 $O(n^2)$ ,一般使用堆(优先队列)进行优化,这样的复杂度是 $O((n + e) \log n)$ 的复杂度,还算优秀,关键是很稳(相对于 $SPFA$ 来说)。

普通的 $Dijkstra$ 其实是跑不了负权边的,还有一个扩展算法叫做 $Johnson$ ,这个算法可以跑负权边,但是复杂度为 $O(V^2logV +VE)$ 。好像有一点鸡肋。。。。

$SPFA$

关于 $SPFA$ 有各种优化,有很多花里胡哨的,但是都可以卡掉。。。。。

详见知乎一贴 $\Rightarrow \Rightarrow$ 链接

自己以前也写过一篇关于 $SPFA$ 的文章,好像到现在还在咕咕咕(逃

扩展

  • $SPFA$ 可以用来求最长路

最简单的思路就是,把松弛操作改一下,然后取最大,这不就可以了吗?但是,这种方法很容易被卡,因为会原地转圈圈。

当然,还有一个非常机智的方法,鉴于 $SPFA$ 可以跑负权边的特点。所以说把每一条边的权值都取反的就可以了,然后跑一边最短路。最后结果再取反,就是正确答案。

次短路

很玄学的一个问题。

$BFS$

首先有一个非常暴力的做法,就是使用 $bfs$ 然后搜索整个图,然后第一个达到终点的就是最短路,第 $k$ 个就是第 $k$ 短路。但是很慢呐~~

正解

可能还有其他的方法,但是正解的思路非常简单,为了让次短路出现,我们直接在最短路上面改一条边就可以了。枚举最短路上每一条路径(可能很多条边连在一起),尝试换掉这一条路径的次小可能值。用公式来说就是这样:

表示从 $s \rightarrow t$ 的最短路中,枚举 $x \rightarrow y$ 这一条路径的次小值。最后枚举完后在这些结果中,选一个最小的就是次小值。

$k$ 短路

emm,非常毒瘤。。。。。

$A*$ (启发式搜索)

emm,既然是新算法我当然决定新建一片博文好好讲讲啦~~

参考资料

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×