欢迎来到天天文库
浏览记录
ID:16033382
大小:228.50 KB
页数:33页
时间:2018-08-07
《09省赛acm算法参考》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、09省赛邵伯仲的算法参考1最短路径解析(1-7页)2中国剩余定理(7-11页)3有重复元素排列问题(11-12)4欧拉回路问题(13-16页)5母函数问题(17-25页)6集合划分问题(25页)7常系数线性递推矩阵乘法(26-30页)33最短路径解析最短路径(ShortestPath)是在实际应用中非常有用的工具,将该问题细分,可以分为点到点最短路径(source-sink),单源点的最短路径(single-source),所有点到所有点(all-pairs)以及带负边情况下的最短路径。为了简化我们的问题,设置以下几个限制:有向
2、图,无向图可以看作每条边对应两条方向相反的有向边无负环,可以想象,如果存在负环则路径值可不断减小,含负环的最短路径是NP的,暂不讨论。单源点最短路径的简单算法单源点最短路径(无负边)可以用Dijkstra算法较好的解决,其思想类似与求最小生成树(MST)的Prim算法。只是Dijkstra将优先队列的权由两点的边改为了从源点到下一点的路径:Prim:Priority=edge.weight()//从v点到w点的weightDijkstra:Priority=wt[v]+edge.weight()//从源点到w点的值,wt[v]表
3、示源点到v点的值注意,wt保存的就是Priority。类似于Prim,Dijkstra算法的复杂度主要取决于优先队列的实现,普通的Dijkstra算法能在线性时间内解决单源点无负边的最短路径问题,即复杂度为V2。采用了优先队列的数据结构后,可以在ElgdV-Elg2V之间解决问题(d表示采用d-堆)。点到点的无负边最短路径也可以用Dijkstra来解决,从源点出发,当搜索到目标点时停止搜索。十分容易理解,我就不罗嗦了。All-Pairs的最短路径问题正如大多数教材中所讲到的,求单源点无负边最短路径用Dijkstra,而求所有点最
4、短路径用Floyd。确实,我们将用到Floyd算法,但是,并不是说所有情况下Floyd都是最佳选择。对于没有学过Floyd的人来说,在掌握了Dijkstra之后遇到All-Pairs最短路径问题的第一反应可能会是:计算所有点的单源点最短路径,不就可以得到所有点的最短路径了吗。简单得描述一下算法就是执行V次Dijkstra算法,自然其复杂度在最优情况下可以是VElgdV。Floyd可以说是Warshall算法的扩展了,三个for循环便可以解决一个复杂的问题,应该说是十分经典的。从它的三层循环可以看出,它的复杂度是V3,除了在第二层
5、for中加点判断可以略微提高效率,几乎没有其他办法再减少它的复杂度。33比较两种算法,不难得出以下的结论:对于稀疏的图,采用V次Dijkstra比较出色,对于茂密的图,可以使用Floyd算法。另外,Floyd可以处理带负边的图。无环网络的最短路径问题无环网络(与DAG略微有区别)较带环网络而言,因为无环,所以边的正负是无所谓的。记得拓扑网络中有的点可能只做源点没有入度,那么在求最短路径中就搜索不到该点了,我们提出多源点的最短路径问题(Multisourceshortestpaths)了描述这种情况下求最短路径。其实我们可以将该问
6、题转化为单源点的最短路径问题,只需加一个哑结点,其指向所有的无入度结点,来作为新的源,而哑结点的所有边权为0。在一般图(带正环)中求最长路径问题,类似在带负环图中求最短路径问题,是NP难的。不过在无环网络中却可以求最长路径,因为无环网络无正环,所以可以确定最长的路径,而且最长路径对于DAG很有意义。所以我们先考虑在DAG中求最长路径(最短路径算法类似):利用DAG的强大武器——拓扑排序,可以避免Dijkstra中使用优先队列的损耗,因此效率高于Dijkstra。只要按拓扑排序后的序列遍历每个结点,刷新每条边,最终就可以得到最长路
7、径了。求多源点的最长或最短路径问题可以在线性时间内解决,即复杂度E。对于所有点的最短路径,我们当然可以运行V次上一段的算法来求,这样复杂度是VE。除此以外,还存在着无环图中求所有点的最短路径,而且它可以避免多次使用拓扑排序。类似于求DAG的传递闭包问题,采用DFS和DP方法,可以得到一个有效的算法。伪代码如下:储存边的二维数组p;储存double的二维数组d;递归的函数(Graph图,int遍历结点v){遍历从v结点出发的所有边:边e=该边;intt=边的另一端;doublew=边的权;若d[s][t]>w,更新d[s][t]=
8、w,p[s][t]=e;若t未遍历,递归遍历t;遍历从t结点出发的所有边:若d[s][i]>w+d[t][i]:更新d[s][i]=w+d[t][i],p[s][i]=e;}该算法复杂度为VE(适用于负边)。33欧几里德网络(EuclideanNetworks)
此文档下载收益归作者所有