当前位置:首页 >> >>

NOI常用算法

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; 1 / 12 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 J<>I 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; 文档收集自网络,仅用于 2 / 12 FOR J:=1 TO N DO IF (S[J]=0) AND (DIST[J]<W) THEN BEGIN M:=J; W:=DIST[J]; END; IF M<>I THEN S[M]:=1 ELSE EXIT; FOR J:=1 TO N DO IF (S[J]=0) AND (DIST[M]+G[M,J]<DIST[J]) THEN BEGIN DIST[J]:=DIST[M]+G[M,J]; PATH[J]:=PATH[M]+[J]; END; END; FOR I:=1 TO N DO IF I<>E THEN BEGIN FOR J:=1 TO N DO IF J IN PATH[I] THEN WRITE(J:3); WRITELN('W=':4,DIST[I]); END; END; BEGIN ASSIGN(INPUT,'DIJKSTRA.IN'); ASSIGN(OUTPUT,'DIJKSTRA.OUT'); RESET(INPUT); REWRITE(OUTPUT); READLN(N,E); CREATEMTX; WRITELN; READLN(I); DIJKSTRA(DIST,PATH,I); WRITELN; CLOSE(INPUT); CLOSE(OUTPUT); END. 2.Floyd-Warshall 3 / 12 1)适用范围: a)APSP(All Pairs Shortest Paths) b)稠密图效果最佳 c)边权可正可负 2)算法描述: a)初始化:dis[u,v]=w[u,v] b)For k:=1 to n For i:=1 to n For j:=1 to n If dis[i,j]>dis[i,k]+dis[k,j] Then Dis[I,j]:=dis[I,k]+dis[k,j]; c)算法结束:dis 即为所有点对的最短路径矩阵 3)算法小结: 此 算 法 简 单 有 效 , 由 于 三 重 循 环 结 构 紧 凑 , 对 于 稠 密 图 , 效 率 要 高 于 执 行 |V| 次 Dijkstra 算法。时间复杂度 O(n^3)。文档收集自网络,仅用于个人学习 考虑下列变形:如(I,j)∈E 则 dis[I,j]初始为1,else 初始为0,这样的 Floyd

更多相关标签: