图论算法源码

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

1、Dijkstra1)适用条件&范围：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)Fori:=1ton1.取V-S中的一顶点u使得dis[u]=min{dis[v]

2、v∈V-S}2.S=S+{u}3.ForV-S中每个顶点vdoRelax(u,v,Wu,v)c)算法结束：dis[i]为s到i的最短距离；pre[i]为i的前驱节点3)

3、算法优化：使用二叉堆(BinaryHeap)来实现每步的DeleteMin(ExtractMin，即算法步骤b中第1步)操作，算法复杂度从O(V^2)降到O((V+E)㏒V)。推荐对稀疏图使用。使用FibonacciHeap(或其他Decrease操作O(1),DeleteMin操作O(logn)的数据结构)可以将复杂度降到O(E+V㏒V)；如果边权值均为不大于C的正整数，则使用RadixHeap可以达到O(E+V㏒C)。但因为它们编程复杂度太高，不推荐在信息学竞赛中使用。注：程序使用二叉堆程序：programmtx_grp;constnum=10;max=10000;typegrp

4、=array[1..num,1..num]ofinteger;rcd=setof1..num;arr=array[1..num]ofinteger;arr2=array[1..num]ofrcd;vari,j,w,m,n,e,k:integer;g:grp;visited:array[1..num]ofboolean;path:arr2;dist,s:arr;procedurecreatemtx;vari,j,k:integer;beginfori:=1tondoforj:=1tondog[i,j]:=max;fork:=1toedobeginreadln(i,j,w);g[i,j]

5、:=w;g[j,i]:=w;end;end;procedureprint(g:grp);beginfori:=1tondobeginforj:=1tondoifg[i,j]=maxthenwrite('oo':4)elsewrite(g[i,j]:4);writeln;end;end;proceduredijkstra(vardist:arr;varpath:arr2;i:integer);begine:=i;forj:=1tondobeginifj<>ithens[j]:=0elses[j]:=1;dist[j]:=g[i,j];ifdist[j]

6、[i]+[j]elsepath[j]:=[];end;fork:=1ton-2dobeginw:=max;m:=i;forj:=1tondoif(s[j]=0)and(dist[j]ithens[m]:=1elseexit;forj:=1tondoif(s[j]=0)and(dist[m]+g[m,j]ethenbeginforj:=1t

7、ondoifjinpath[i]thenwrite(j:3);writeln('w=':4,dist[i]);end;end;beginassign(input,'nodelst5.in');reset(input);readln(n,e);createmtx;writeln;readln(i);dijkstra(dist,path,i);writeln;end.2.Floyd-Warshall1)适用范围：a)APSP(AllPairsShortestPaths)b)稠密图效果最佳c)边权可正可负2)算法描述：a)初始化：dis[u,v]=w[u,v]b)Fork:=1tonFor

8、i:=1tonForj:=1tonIfdis[i,j]>dis[i,k]+dis[k,j]ThenDis[I,j]:=dis[I,k]+dis[k,j];c)算法结束：dis即为所有点对的最短路径矩阵3)算法小结：此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行

9、V

10、次Dijkstra算法。时间复杂度O(n^3)。考虑下列变形：如(I,j)∈E则dis[I,j]初始为1,else初始为0，这样的Floyd算法最后的最短路径矩阵即成为一个判断