《几个基本算法.docVIP

一、图论算法 Relaxation(松弛操作)： procedure relax(u,v,w:integer);//多数情况下不需要单独写成procedure。 begin if dis[u]+wdis[v] then begin dis[v]:=dis[u]+w; pre[v]:=u; end end; Dijkstra 适用条件范围： 单源最短路径i,j)∈E都有Wij≥0); 算法描述： 初始化：dis[v]=maxint(v∈V,v≠s); dis[s]=0; pre[s]=s; S={s}; For i:=1 to n 1.取V-S中的一顶点u使得dis[u]=min{dis[v]|v∈V-S} 2.S=S+{u} 3.For V-S中每个顶点v do Relax(u,v,Wu,v) 算法结束：dis[i]为s到i的最短距离；pre[i]为i的前驱节点 算法优化： 使用二叉堆(Binary Heap)来实现每步的DeleteMin(ExtractMin，即算法步骤b中第1步)操作，算法复杂度从O(V^2)降到O((V+E)㏒V)。推荐对稀疏图使用。 使用Fibonacci Heap(或其他Decrease操作O(1),DeleteMin操作O(logn)的数据结构)可以将复杂度降到O(E+V㏒V)；如果边权值均为不大于C的正整数，则使用Radix Heap可以达到O(E+V㏒C)。但因为它们编程复杂度太高，不推荐在信息学竞赛中使用。 程序： 注：程序使用二叉堆 Bellman-Ford 适用条件范围： 单源最短路径If dis[u]+wdis[v] Then Exit(False) 算法时间复杂度O(VE)。因为算法简单，适用范围又广，虽然复杂度稍高，但因为它实践中的效果不错，仍不失为一个很实用的算法。 程序： 菜鱼有话说： 这个……N久前有人提出个叫“SPFA”的东西，主要思想是：维护一队列，对队头的顶点u，枚举它的邻接边，如果它可以用来更新顶点v，则更新v的dis。更新后，如果顶点不在队中，则加入队。重复，直至队列空。有人说这个算法是O(kE)，k平均为2。看完算法的描述，我直观上就感觉这是bellman-ford的一种实现方式，但无奈没有证据，在与Zroge和Amber的讨论中没有能说明。但是，偶尔翻起一本书《Data structures and Algorithm analysis》，终于确定所谓SPFA就是Bellman-Ford（如果以上算法描述的确是SPFA的描述的话）。如有怀疑可以参考此书，网上有CHM电子书。既然是Bellman-Ford，它的算法复杂度就是O(VE)。而实际上，对于这个所谓“SPFA”是可以很轻易构造出使它复杂度为VE的例子的（有负权回路即可）。 以上为我个人说法，有不同观点可以讨论。 Topological Sort(拓扑排序) 适用条件范围： AOV网(Activity On Vertex Network); 有向图; 作为某些算法的预处理过程(如DP) 算法描述： 很简单的算法：每次挑选入度为0的顶点输出(不计次序)。 如果最后发现输出的顶点数小于|V|，则表明有回路存在 算法实现： 数据结构： adj:邻接表;有4个域{u,v,w,next} indgr[i]:顶点i的入度; stack[]:栈 初始化:top=0 (栈顶指针) 将初始状态所有入度为0的顶点压栈 I=0 (计数器) While 栈非空(top0) do 顶点v出栈；输出v；计数器增1； For 与v邻接的顶点u do dec(indgr[u]); If indgr[u]=0 then 顶点u入栈 EXIT(I=|V|) 简单高效实用的算法。上述实现方法复杂度O(V+E) 程序： SSSP(Single-source shortest path) On DAG 适用条件范围： DAG(Directed Acyclic Graph,有向无环图); 边权可正可负 算法描述： Toposort; If Toposort=False Then HALT(Not a DAG) For 拓扑序的每个顶点u do For u的每个邻接点v do Relax(u,v,w); 算法结束后：如有环则输出错误信息；否则dis[i]为s到i的最短距离，pre[i]为前驱顶点。 算法实现： 基本从略。此算法时间复杂度O(V+E)，时间编程 复杂度低，如遇到符合条件的题目(DAG)，推荐使用。 还有，此算法的步骤c可以在toposort中实现，这样即减小了此算法复杂度的一个系数。 程序：