From bd20bbff94201243b6b265b937b3d43a43326c01 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 2 Feb 2015 13:17:58 +0100 Subject: [PATCH] Dijkstra: Oprava preklepu Diky, Jethro. --- 2-dinic/2-dinic.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/2-dinic/2-dinic.tex b/2-dinic/2-dinic.tex index e6c6944..e3f36ae 100644 --- a/2-dinic/2-dinic.tex +++ b/2-dinic/2-dinic.tex @@ -218,7 +218,7 @@ maxim Za jednu iteraci velkého cyklu projdeme malým cyklem maximálnì tolikrát, o kolik se v nìm zvedl tok, proto¾e ka¾dá zlep¹ující cesta ho zvedne alespoò o $1$. Zlep¹ující cesta se tedy hledá maximálnì $\vert f\vert$-krát za celou dobu bìhu algoritmu. -Cestu najedeme v èase $\O(n)$. Celkem na~hledání +Cestu najdeme v èase $\O(n)$. Celkem na~hledání cest spotøebujeme $\O(\vert f\vert\cdot n)$ za celou dobu bìhu algoritmu. Nesmíme ale zapomenout na èi¹tìní. V jedné iteraci velkého cyklu nás stojí èi¹tìní $\O(m)$ a velkých -- 2.39.2