圖論算法源碼

《圖論算法源碼》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、Dijkstra1)適用條件&范圍：a)單源最短路徑(從源點(diǎn)s到其它所有頂點(diǎn)v);b)有向圖&無向圖(無向圖可以看作(u,v),(v,u)同屬于邊集E的有向圖)c)所有邊權(quán)非負(fù)(任取(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中的一頂點(diǎn)u使得dis[u]=min{dis[v]

2、v∈V-S}2.S=S+{u}3.ForV-S中每個(gè)頂點(diǎn)vdoRelax(u,v,Wu,v)c)算法結(jié)束：dis[i]為s到i的最短距離；pre[i]為i的前驅(qū)節(jié)點(diǎn)3)

3、算法優(yōu)化：使用二叉堆(BinaryHeap)來實(shí)現(xiàn)每步的DeleteMin(ExtractMin，即算法步驟b中第1步)操作，算法復(fù)雜度從O(V^2)降到O((V+E)㏒V)。推薦對稀疏圖使用。使用FibonacciHeap(或其他Decrease操作O(1),DeleteMin操作O(logn)的數(shù)據(jù)結(jié)構(gòu))可以將復(fù)雜度降到O(E+V㏒V)；如果邊權(quán)值均為不大于C的正整數(shù)，則使用RadixHeap可以達(dá)到O(E+V㏒C)。但因?yàn)樗鼈兙幊虖?fù)雜度太高，不推薦在信息學(xué)競賽中使用。注：程序使用二叉堆程序：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)邊權(quán)可正可負(fù)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)算法結(jié)束：dis即為所有點(diǎn)對的最短路徑矩陣3)算法小結(jié)：此算法簡單有效，由于三重循環(huán)結(jié)構(gòu)緊湊，對于稠密圖，效率要高于執(zhí)行

9、V

10、次Dijkstra算法。時(shí)間復(fù)雜度O(n^3)。考慮下列變形：如(I,j)∈E則dis[I,j]初始為1,else初始為0，這樣的Floyd算法最后的最短路徑矩陣即成為一個(gè)判斷