Dinic算法（又称Dinitz算法）是一个在网路流中计算最大流的强多项式複杂度的算法，构想由以色列（前苏联）的计算机科学家Yefim (Chaim) A. Dinitz在1970年提出。
基本介绍
- 中文名：Dinic算法
- 外文名：dinic algorithm
- 说明：网路流最大流的最佳化算法之一
- 时间複杂度：O(n^2*m)
- 补充：相关代码
历史
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、根据残量网路计算层次图。
2、在层次图中使用DFS进行增广直到不存在增广路。
3、重複以上步骤直到无法增广。
时间複杂度
因为在Dinic的执行过程中，每次重新分层，汇点所在的层次是严格递增的，而n个点的层次图最多有n层，所以最多重新分层n次。在同一个层次图中，因为每条增广路都有一个瓶颈，而两次增广的瓶颈不可能相同，所以增广路最多m条。搜寻每一条增广路时，前进和回溯都最多n次，所以这两者造成的时间複杂度是O(nm)；而沿着同一条边(i,j)不可能枚举两次，因为第一次枚举时要幺这条边的容量已经用尽，要幺点j到汇不存在通路从而可将其从这一层次图中删除。综上所述，Dinic算法时间複杂度的理论上界是O(n^2*m)。
代码实现
递归实现
代码简短，效率略低。（不是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_engivoidDinic(){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;TypeLx=Array[0..50]OfLongint;VarLu: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);VarI,J,Now,Sum:Longint;BeginFillchar(D,Sizeof(D),0);Fillchar(V,Sizeof(V),False);ForJ:=1 To N DoDist[J]:=MaxLongint;Dist[S]:=0;V[S]:=True;D[1]:=S;Head:=1;Tail:=1;While Head<=Tail DoBeginNow:=D[Head];ForI:= 1 To B[Now,0] Do if A[Now,B[Now,I]]>0 thenIf(Dist[B[Now,I]]>Dist[Now]+1) ThenBeginDist[B[Now,I]]:=Dist[Now]+1;If Not V[B[Now,I]] ThenBeginInc(Tail);D[Tail]:=B[Now,I];V[B[Now,I]]:=True;End;End;Inc(Head);End;End;Procedure Dfs(X,D:Longint);VarI:Longint;BeginLu[D]:=X;T[X]:=True;If X=N ThenBeginC:=False;S:=D;End;For I:=1 To N DoIf(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);VarI,J,K:Longint;BeginK:=MaxLongint;ForI:=2 To Len DoIf 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 DoBeginDec(A[L[I-1],L[I]],K);Inc(A[L[I],L[I-1]],K);End;End;BeginRead(N,M);ForI:=1 To M DoBeginRead(X,Y,K);A[X,Y]:=K;Inc(B[X,0]);B[X,B[X,0]]:=Y;End;C:=False;While True DoBeginSpfa(1);ForI:=1 To N DoT[I]:=False;K:=MaxLongint;C:=True;Dfs(1,1);If C Then Break;Expand(Lu,S);Inc(Ans,Sum);End;Writeln(Ans);End.