-
Dinic算法
鎖定
- 中文名
- Dinic算法
- 外文名
- dinic algorithm
- 説 明
- 網絡流最大流的優化算法之一
- 時間複雜度
- O(n^2*m)
- 補 充
- 相關代碼
Dinic算法歷史
Yefim Dinitz在Adel'son-Vel'sky(AVL樹的發明者之一)的算法課的課前活動上發明了這個算法。當時他不知道關於Ford–Fulkerson算法的基本事實。
Dinitz在1969年一月向他人公佈了他發明的算法,又在1970年將其發佈在Doklady Akademii nauk SSSR雜誌上。 在1974年,Shimon Even和(他之後的博士學生)Alon Itai在海法的以色列理工學院對Dinitz的算法以及Alexander Karzanov的阻塞流的想法很感興趣。但是雜誌上的文章每篇的篇幅被限制在四頁以內,很多細節都被忽略,這導致他們很難根據文章還原出算法。但他們沒有放棄,在後三天不斷地努力,設法瞭解這兩個文件中的分層網絡的維護問題。 在接下來的幾年,Even由於在講學中將Dinitz念為Dinic,導致Dinic算法反而成為了它的名稱。 Even和Itai也將算法與BFS和DFS結合起來,形成了當前版本的算法。
在Ford–Fulkerson算法被髮明之後的約十年之內,使算法能在多項式複雜度之內處理不合理的邊界的方法是未知的。這造成缺乏任何已知的多項式複雜度算法解決最大流問題。 Dinitz算法和Edmonds–Karp算法在1972年發佈,證明在Ford–Fulkerson算法中,如果每次總選擇最短的一條增廣路,路徑長度將單調增加,且算法總能終止。
[1]
Dinic算法算法介紹
Dinic算法層次圖
Dinic算法算法流程
1、根據殘量網絡計算層次圖。
2、在層次圖中使用DFS進行增廣直到不存在增廣路。
3、重複以上步驟直到無法增廣。
Dinic算法時間複雜度
因為在Dinic的執行過程中,每次重新分層,匯點所在的層次是嚴格遞增的,而n個點的層次圖最多有n層,所以最多重新分層n次。在同一個層次圖中,因為每條增廣路都有一個瓶頸,而兩次增廣的瓶頸不可能相同,所以增廣路最多m條。搜索每一條增廣路時,前進和回溯都最多n次,所以這兩者造成的時間複雜度是O(nm);而沿着同一條邊(i,j)不可能枚舉兩次,因為第一次枚舉時要麼這條邊的容量已經用盡,要麼點j到匯不存在通路從而可將其從這一層次圖中刪除。綜上所述,Dinic算法時間複雜度的理論上界是O(n^2*m)。
Dinic算法代碼實現
遞歸實現
代碼簡短,效率略低。(不是dinic,是最短路徑增值)
boolbuild()//建立層次圖 { intx,y; memset(d,-1,sizeof(d)); memset(G,-1,sizeof(G)); bg=ed=d[s]=0;Q[ed++]=s;G[s]=g[s]; while(bg<ed) { x=Q[bg++]; for(inti=g[x];i+1;i=np) { y=to; if(cap&&d[y]==-1) { d[y]=d[x]+1;G[y]=g[y]; if(y==t)returntrue; Q[ed++]=y; } } } returnfalse; } intfind(intx,intlow=inf)//進行增廣 { if(x==t)returnlow; intret=0,y; for(int&i=G[x];i+1;i=np)//注意i是引用 { y=to[i]; if(cap[i]&&d[y]==d[x]+1&&(ret=find(y,low<?cap[i]))) { cap[i]-=ret;cap[vp]+=ret; returnret; } } return0; } intdinic()//主過程 { intflow,ret=0; while(build()) while(flow=find(s)) ret+=flow; returnret; }
非遞歸實現
效率更高,但代碼量略有些大。 //Author:dd_engi voidDinic() { for(;;){ BFS(); if(D[T]==-1)break; intpath_n=0; intx=S; memcpy(cur,E,sizeof(cur)); for(;;){ if(x==T){ intmink=-1,delta=INT_MAX; for(inti=0;i<path_n;++i){ if(path[i]->c<delta){ delta=path[i]->c; mink=i; } } for(inti=0;i<path_n;++i){ path[i]->c-=delta; path[i]->back->c+=delta; } path_n=mink; x=path[path_n]->x; } edge*e; for(e=cur[x];e;e=e->next){ if(e->c==0) continue; inty=e->y; if(D[x]+1==D[y]) break; } cur[x]=e; if(e){ path[path_n++]=e; x=e->y; } else{ if(path_n==0) break; D[x]=-1; --path_n; x=path[path_n]->x; } } } }
PASCAL代碼實現
ProgramDinic; Type Lx=Array[0..50]OfLongint; Var Lu:Lx; A,B:Array[0..50]Of Lx; D,Dist:LX; V,T:Array[0..50]Of Boolean; Head,Tail,Sum,Ans,X,Y,S,I,P,J,K,M,N:Longint; Q,C:Boolean; ProcedureSpfa(S:Longint); Var I,J,Now,Sum:Longint; Begin Fillchar(D,Sizeof(D),0); Fillchar(V,Sizeof(V),False); ForJ:=1 To N Do Dist[J]:=MaxLongint; Dist[S]:=0; V[S]:=True; D[1]:=S; Head:=1; Tail:=1; While Head<=Tail Do Begin Now:=D[Head]; ForI:= 1 To B[Now,0] Do if A[Now,B[Now,I]]>0 then If(Dist[B[Now,I]]>Dist[Now]+1) Then Begin Dist[B[Now,I]]:=Dist[Now]+1; If Not V[B[Now,I]] Then Begin Inc(Tail); D[Tail]:=B[Now,I]; V[B[Now,I]]:=True; End; End; Inc(Head); End; End; Procedure Dfs(X,D:Longint); Var I:Longint; Begin Lu[D]:=X; T[X]:=True; If X=N Then Begin C:=False; S:=D; End; For I:=1 To N Do If(A[X,I]>0)And C And(NotT[I])And(Dist[X]+1=Dist[I]) Then Dfs(I,D+1); End; Procedure Expand(L:Lx;Len:Longint); Var I,J,K:Longint; Begin K:=MaxLongint; ForI:=2 To Len Do If K>A[L[I-1],L[I]] Then K:=A[L[I-1],L[I]]; Sum:=K; Writeln('K=',K); For I:=2 To Len Do Begin Dec(A[L[I-1],L[I]],K); Inc(A[L[I],L[I-1]],K); End; End; Begin Read(N,M); ForI:=1 To M Do Begin Read(X,Y,K); A[X,Y]:=K; Inc(B[X,0]); B[X,B[X,0]]:=Y; End; C:=False; While True Do Begin Spfa(1); ForI:=1 To N Do T[I]:=False; K:=MaxLongint; C:=True; Dfs(1,1); If C Then Break; Expand(Lu,S); Inc(Ans,Sum); End; Writeln(Ans); End.