算法设计与分析课件 48 Dinic算法

算法设计与分析本节要点CONTENTSDinic算法Dinic算法Dinic算法（又称Dinitz算法）是一个在网络流中计算最大流的多项式复杂度的算法，设想由以色列（前苏联）的计算机科学家Yefim(Chaim)A.Dinitz在1970年提出。最短增广路EK算法每次BFS找到一条增广路，增流后，需要重新BFS找下一条增广路，直到找不到增广路为止。Dinic算法，首先从源点出发BFS分“层”，然后从源点出发DFS，沿着d[y]=d[x]+1的边（x，y）找增广路，一次DFS可以实现多次增广，这正是Dinic算法的巧妙之处。Dinic算法算法步骤：1）在残余网络上BFS构造分层图；2）在层次图中DFS找增广路，进行增流，直到不存在增广路。3）重复以上步骤直到无法增广。Dinic算法（1）在残余网络上，从源点出发进行广度优先搜索，构造分层图。Dinic算法（2）在层次图中进行深度优先搜索，找到第1条增广路1-2-4-6。先从节点6回溯到节点4，再从节点4回溯到节点2，回溯时增流8（同向边减8，反向边加8）。Dinic算法节点2还有一个邻接点5，从节点2出发继续进行深度优先搜索，又找到增广路2-5-6，回溯时增流2。因为1-2的可增量为10，2-4已经增流8，所以从节点2出发还可以增流2。Dinic算法回溯到节点1，回溯时增流10（从1到2的边减10，从2到1的边加10）。Dinic算法节点1还有一个邻接点3，从节点1出发继续进行深度优先搜索，找到增广路1-3-5-6，回溯时增流7（同向边减7，反向边加7）。Dinic算法（3）再次从源点出发进行广度优先搜索，构造分层图。Dinic算法（4）在层次图中进行深度优先搜索，找到1-3-2，此时从节点2出发无法沿着层次加1且cap>flow的方向行进，增流为0，修改d[2]=0。回溯到节点3。Dinic算法节点3还有一个邻接点5，从节点3出发继续进行深度优先搜索，找到增广路1-3-5-4-6，回溯时增流6（同向边减6，反向边加6）。Dinic算法（5）再次从源点出发进行广度优先搜索，构造分层图，无法到达汇点，结束，最大流为23。算法实现Dinic算法算法分析时间复杂度：每次重新分层，最多有V层，最多重新分层V次。关键边的总数为O(VE)，总的时间复杂度为O(V2E)，其中，V为结点个数，E为边的数量。Dinic算法一般可以处理104~105规模的网络。空间复杂度：用到了一些辅助数组，空间复杂度为O(V)。Dinic算法当前弧优化是指记录节点u当前正在考查的弧cur[u]，已经满流的边无须访问，从而避免重复访问。例如，对x→u这条路径进行增广时，节点u的前两条边a和b已经满流，最后一次考查的弧为cur[u]（未满流）。当从另一条路径x→y→u搜索时，就可以从cur[u]开始访问，无须再访问边a和b。Dinic算法—当前弧优化当前弧优化的Dinic算法，分层部分无任何变化，只需以下3处改动。（1）在增流之前初始化当前弧cur[]。（2）在更新i时，需要将cur[]和i一起更新。最简单的办法是在i的前面添加引用符号&，这样i和cur[]便指向同一存储空间，因而更新时必然同步。Dinic算法—当前弧优化（3）可增量（余量）reset为0时，需要立即跳出循环，以避免当reset为0时仍更新i和cur[]。因为当可增量reset为0时，只能说明这条增广路没有可增量，而当前弧可能仍未满流，其他的增广路仍然可以通过当前弧增流。Dinic算法—当前弧优化算法实现Dinic算法—当前弧优化算法分析时间复杂度：