一般图
复杂度主要取决于dfs增广的过程。
将dfs部分的复杂度分成两部分来分析：1）修改增广路上边的流量。至多会增广$m$次，一条增广路的长度至多是$n$，所以这一部分的复杂度是$O(nm)$。2）dfs遍历时找增广路失败时经过的边。由于一旦从某条边出发找最短路失败了，我们就不会再走那条边（当前弧优化），所以这一部分的复杂度是$O(m)$的。故而dfs增广的复杂度是$O(nm)$。
而由于每一次重新建分层图，残余网络上$s$到$t$的最短路长度一定会增加，所以至多重建$n-1$次图。
故dinic的运行时间上界为$O(n^2m)$。
单位图 (unit graph)
定义
单位图(unit graph) 是指，所有的边的容量都是整数，且每一个不是$s$或$t$的点，要么出度为$1$，连出去的边容量为$1$，要么入度为$1$，连进来的边容量为$1$。
复杂度分析
在单位图上，至多进行$2\lceil \sqrt {n-2}\rceil$次dfs增广。
考虑某一次dfs增广时，现在已经得到了的流为$f$，最大流为$f^$，$R$为$f$的残留网络。则$f^ - f$是$R$上的一个流，并且$R$是单位图。我们必然可以将$f^ - f$上容量为$1$的边划分成$|f^| - |f|$条从$s$到$t$的路径（可能还有一些环）。由于$R$是单位图，所以除了$s,t$以外的任意一个点至多属于一条路径，所以最短路径的长度至多为${n-2\over |f^*|-|f|} + 1$。
经过$\lceil\sqrt {n-2}\rceil$次dfs增广之后，最短路的长度至少是$\sqrt{n-2} + 1$，所以$\sqrt{n-2} + 1 \le {n-2\over |f^|-|f|} + 1$，所以$|f| - |f| \le \sqrt{n-2}$，所以至多再进行$\sqrt{n-2}$次增广就可以结束算法。
所以单位图上Dinic的复杂度为$O(nm\sqrt n)$。
参考资料：Tarjan, R.E. Data structures and network algorithms. 1983. Page 102.
边的容量为$1$的图
对于边的容量为$1$的图，Dinic至多进行$O(\min\{n^{2\over 3},m^{1\over 2}\})$次dfs增广。
a) dfs增广次数不超过$O(n^{2\over 3})$
Lemma 3：给出一张边容量为$1$的图，设最大流为$M$，则残余网络的从$s$到$t$的最短路的长度至多是$2n\over \sqrt M$。
证明：设最短路的长度为$l$，从$s$到它的最短路长度为$i$的点集是$V_i$，则$|V_i| \cdot |V_{i+1}| \ge M$，所以$|V_i|\ge \sqrt M$或者$|V_{i+1}| \ge \sqrt M$。又因为$\sum |V_i| = n$，所以$\lfloor {l+1\over 2}\rfloor \cdot \sqrt M \le n$。所以有$l \le {2n\over \sqrt M}$。
Dinic算法的过程中，当已经得到的流量$F$其大小不到$M - n^{2\over 3}$时，残余网络的最大流至少为$M-F=n^{2\over 3}$，残余网络的最短路的长度$l\le {2n \over \sqrt{n^{2\over 3}}} = 2n^{2\over 3}$。所以在$F\le M-n^{2\over 3}$的时候至多进行$O(n^{2\over 3})$次dfs增广。当$F>M-n^{2\over 3}$的时候，残余网络的最大流不超过$n^{2\over 3}$，至多进行$n^{2\over 3}$次dfs增广。故进行dfs增广的次数上界是$O(n^{2\over 3})$。
b) dfs增广次数不超过$O(m^{1\over 2})$
与前面单位图的证明类似，可以将$f^ - f$中的边划分成$|f^|-|f|$条不相交的路径，由于每条边至多属于一条路径，所以路径长度的最小值不大于$m\over |f^|-|f|$。经过$\sqrt m$次Dinic增广以后，路径的长度不小于$\sqrt m$，所以$\sqrt m \le {m\over |f^| - |f|}$，所以$|f^*|-|f|\le \sqrt m$，所以至多再增广$\sqrt m$次就可以结束。
所以在边的容量为$1$的图中，Dinic算法的复杂度为$O(\min\{n^{2\over 3},m^{1\over 2} \}\cdot nm)$
参考资料：Even, Shimon; Tarjan, R. Endre. Network Flow and Testing Graph Connectivity. SIAM Journal on Computing. 1975, 4 (4): 507–518