複製鏈接
請複製以下鏈接發送給好友

Dinic算法

鎖定
Dinic算法(又稱Dinitz算法)是一個在網絡流中計算最大流的強多項式複雜度的算法,設想由以色列(前蘇聯)的計算機科學家Yefim (Chaim) A. Dinitz在1970年提出。
中文名
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算法層次圖

層次圖,就是把原圖中的點按照點到源的距離分“層”,只保留不同層之間的邊的圖。 [1] 

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.

參考資料
  • 1.    Even, Shimon; Tarjan, R. Endre. Network Flow and Testing Graph Connectivity. SIAM Journal on Computing. 1975, 4 (4): 507–518. ISSN 0097-5397. doi:10.1137/0204043.