NOI常用算法.docVIP

1.Dijkstra 1)适用条件范围： a)单源最短路径(从源点s到其它所有顶点v); b)有向图无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图) c)所有边权非负(任取(i,j)∈E都有Wij≥0); 2)算法描述： a)初始化：dis[v]=maxint(v∈V,v≠s); dis[s]=0; pre[s]=s; S={s}; b)For i:=1 to n Begin 取V-S中的一顶点u使得dis[u]=min{dis[v]|v∈V-S} S=S+{u} For V-S中每个顶点v do Relax(u,v,Wu,v) End; c)算法结束：dis[i]为s到i的最短距离；pre[i]为i的前驱节点 3)算法优化： 使用二叉堆(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)。但因为它们编程复杂度太高，不推荐在信息学竞赛中使用。 注：程序使用二叉堆 4)程序： PROGRAM DIJKSTRA; CONST NUM=10; MAX=10000; TYPE GRP=ARRAY[1..NUM,1..NUM] OF INTEGER; RCD=SET OF 1..NUM; ARR=ARRAY[1..NUM] OF INTEGER; ARR2=ARRAY[1..NUM] OF RCD; VAR I,J,W,M,N,E,K:INTEGER; G:GRP;VISITED:ARRAY[1..NUM] OF BOOLEAN; PATH:ARR2; DIST,S:ARR; PROCEDURE CREATEMTX; VAR I,J,K:INTEGER; BEGIN FOR I:=1 TO N DO FOR J:=1 TO N DO G[I,J]:=MAX; FOR K:=1 TO E DO BEGIN READLN(I,J,W); G[I,J]:=W; G[J,I]:=W; END; END; PROCEDURE PRINT(G:GRP); BEGIN FOR I:=1 TO N DO BEGIN FOR J:=1 TO N DO IF G[I,J]=MAX THEN WRITE(OO:4) ELSE WRITE(G[I,J]:4); WRITELN; END; END; PROCEDURE DIJKSTRA(VAR DIST:ARR;VAR PATH:ARR2;I:INTEGER); BEGIN E:=I; FOR J:=1 TO N DO BEGIN IF JI THEN S[J]:=0 ELSE S[J]:=1; DIST[J]:=G[I,J]; IF DIST[J]MAX THEN PATH[J]:=[I]+[J] ELSE PATH[J]:=[]; END; FOR K:=1 TO N-2 DO BEGIN W:=MAX; M:=I; FOR J:=1 TO N DO IF (S[J]=0) AND (DIST[J]W) THEN BEGIN M:=J; W:=DIST[J]; END; IF MI THEN S[M]:=1 ELSE EXIT