算法大全(c,c )（algorithm daquan (c, c )）

《算法大全(c,c )（algorithm daquan (c, c )）》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法大全(c,c++)（AlgorithmDaquan(C,c++)）SolvingtheshortestpathofsinglesourcepointbyA.labelingmethod:VarA:array[1..Maxn,1..Maxn]ofinteger;B:array[1..Maxn]ofinteger;{b[i]referstotheshortestpathfromvertexitosourcepoint}Mark:array[1..Maxn]ofboolean;Procedurebhf;VarBest,best_j:integer;BeginFillchar

2、(mark,sizeof(mark),false);Mark[1]:=true;b[1]:=0;{1assourcepoint}RepeatBest:=0;Fori:=1tondoIfmark[i]then{everypointthathascalculatedtheshortestpath}Forj:=1tondoIf(notmark[j])and(a[i,j]>0)thenIf(best=0)or(b[i]+a[i,j]0thenbeginB[best_j]:=

3、best;mark[best_j]:=true;End;Untilbest=0;End;{bhf}B.Floyedalgorithmsolvestheshortestpathbetweenallvertexpairs:Procedurefloyed;BeginForI:=1tondoForj:=1tondoIfa[I,j]>0thenp[I,j]:=Ielsep[I,j]:=0;{p[I,j]representstheprecursornodeofJontheshortestpathfromItoj}Fork:=1tondo{enumerationintermediate

4、node}Fori:=1tondoForj:=1tondoIfa[i,k]+a[j,k]

5、0:integer);BeginFillchar(mark,sizeof(mark),false);Fori:=1tondobeginD[i]:=a[v0,i];Ifd[i]<>0thenpre[i]:=v0elsepre[i]:=0;End;Mark[v0]:=true;Repeat{everycycleaddsanodeclosesttothe1setandadjuststheparametersofothernodes}Min:=maxint;u:=0;{urecordsthenearestnodefromthe1set}Fori:=1tondoIf(notmark

6、[i])and(d[i]0thenbeginMark[u]:=true;Fori:=1tondoIf(notmark[i])and(a[u,i]+d[u]

7、,sizeof(T),false);Fork:=1tondoForI:=1tondoForj:=1tondoT[I,j]:=t[I,j]or(t[I,k]andt[k,j]);End;Connectedcomponentsof4.undirectedgraphsA.depthfirstProcedureDFS(now,color:integer);BeginFori:=1tondoIfa[now,i]andc[i]=0thenbegin{nodeIstaining}C[i]:=color;DFS(I,color);End;En