图论算法论文

《图论算法论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1.Dijkstra(迪克斯屈拉算法)1)适用条件&范围：a)单源最短路径(从源点s到其它所有顶点v);b)有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图)c)所冇边权非负(任取(i,j)eE都冇WiQO);2)算法描述：a)初始化：dis[v]二maxint(vWV,vHs);dis[s]二0;pre[s]=s;S二{s};b)Fori:=1ton1.取V-S中的一顶点u使得dis[u]=min{dis[v]

2、vEV-S}2.S=S+{u}3.ForV~S中每个顶点vdoRelax(u,v,Wu

3、,v)c)算法结束：dis[i]为s到i的最短距离；pre[i]为i的前驱节点3)算法优化：使用二叉堆(BinaryHeap)来实现每步的DeleteMin(ExtractMin,即算法步骤b中第1步)操作,算法复杂度从0(厂2)降到0((V+E)logV)。推荐对稀疏图使用。使用FibonacciIIeap(或其他Decrease操作0(1),DeleteMin操作0(logn)的数据结构)可以将复朵度降到O(E+VlogV)；如果边权值均为不大于C的」F整数，则使用RadixHeap可以达到0(E+VlogC)。但因为

4、它们编程复杂度太高，不推荐在信息学竞赛屮使用。注：程序使用二叉堆程序：programmtx_grp;constnum=10;max二10000;typegrp=array[1..num,1..num]ofinteger;rcd=setof1..num;arr=array[1..num]ofinteger;arr2=array[1..num]ofred;i,j,w,m,n,e,k:integer;g：grp；visited:array[1..num]ofbooIean;path:arr2;dist,s:arr;procedu

5、recreatemtx;vari,j,k:integer;beginfori:二1tondoforj:=1tondog[i,j]:二max;fork:二1toedobeginreadIn(i,j,w);g[i,j]：二w;g[j,i]：二w;end;end;procedureprint(g:grp);beginfori:二1tondobeginforj:二1tondoifg[i,j]二maxthenwriteCoo":4)eIsewrite(g[i,j]:4);writeIn;end;end;proceduredijkst

6、ra(vardist:arr;varpath:arr2;i:integer);begine:=i;forj:二1tondobeginifjOithens[j]:=0eIses[j]:=1;dist[j]:二g[i,j];ifdist[j]

7、ithens[m]:=1eIseexit;forj:二1tondoif(s[j]二0)and(dist[m]+g[m,j]ethenbeginforj:二1tondoifjinpath[i]thenwrite(j:3);writeln('w二'：4,dist[i]);end;end;beginassign(input,'nodeIst5.in');r

8、eset(input);readIn(n,e);createmtx;writeIn;readIn(i);dijkstra(dist,path,i);writeln;end.2.Floyd-WarshaIID适用范围：a)APSP(A11PairsShortestPaths)b)稠密图效果最佳c)边权可正可负2)算法描述：a)初始化：dis[u,v]=w[u,v]b)Fork:=ltonFori:=1tonForj:=1tonIfdis[i,j]>dis[i,k]+dis[k,j]ThenDis[I,j]:二dis[I,k]

9、+dis[k,j];c)算法结束:dis即为所冇点对的最短路径矩阵3)算法小结：此算法简单冇效，由三重循环结构紧凑，对于稠密图，效率耍高于执行IV

10、次Dijkstra算法。时间复杂度0(13)。考虑下列变形：女D(I,j)eE则dis[I,j]初始为l,else初始为0,这样的Floyd算法最后的最短路