diff options
| author | Gloria Mundi <gloria@gloria-mundi.eu> | 2025-02-13 22:07:35 +0100 |
|---|---|---|
| committer | Gloria Mundi <gloria@gloria-mundi.eu> | 2025-02-13 22:07:35 +0100 |
| commit | 04ca8f7bd16c0c855f604188d617a1bf2e8eacfd (patch) | |
| tree | c0b535dc4635bf7d99c714f030578c73ba023310 /content | |
| parent | 7dc90ef744cf16ac4b4cb4e7d22f4c4686ae7225 (diff) | |
rename Dinic to Dinitz
Diffstat (limited to 'content')
| -rw-r--r-- | content/graph/dinitzScaling.cpp (renamed from content/graph/dinicScaling.cpp) | 0 | ||||
| -rw-r--r-- | content/graph/graph.tex | 4 | ||||
| -rw-r--r-- | content/other/other.tex | 2 |
3 files changed, 3 insertions, 3 deletions
diff --git a/content/graph/dinicScaling.cpp b/content/graph/dinitzScaling.cpp index fd82296..fd82296 100644 --- a/content/graph/dinicScaling.cpp +++ b/content/graph/dinitzScaling.cpp diff --git a/content/graph/graph.tex b/content/graph/graph.tex index 6e8e20b..0692d20 100644 --- a/content/graph/graph.tex +++ b/content/graph/graph.tex @@ -215,12 +215,12 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/pushRelabel.cpp} } -\subsubsection{\textsc{Dinic}'s Algorithm mit Capacity Scaling} +\subsubsection{\textsc{Dinitz}'s Algorithm mit Capacity Scaling} \begin{methods} \method{maxFlow}{doppelt so schnell wie \textsc{Ford-Fulkerson}}{\abs{V}^2\cdot\abs{E}} \method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1} \end{methods} -\sourcecode{graph/dinicScaling.cpp} +\sourcecode{graph/dinitzScaling.cpp} \begin{algorithm}{Min-Cost-Max-Flow} \begin{methods} diff --git a/content/other/other.tex b/content/other/other.tex index 8896962..dce0f3d 100644 --- a/content/other/other.tex +++ b/content/other/other.tex @@ -123,7 +123,7 @@ c'(s',v)&=\sum_{u\in{}V}d(u,v)&c'(v,t')&=\sum_{u\in{}V}d(v,u)\\[-0.5ex]
c'(u,v)&=c(u,v)-d(u,v)&c'(t,s)&=x
\end{align*}
- Löse Fluss auf $G'$ mit \textsc{Dinic's Algorithmus}, wenn alle Kanten von $s'$ saturiert sind ist der Fluss in $G$ gültig. $x$ beschränkt den Fluss in $G$ (Binary-Search für minflow, $\infty$ sonst).
+ Löse Fluss auf $G'$ mit \textsc{Dinitz's Algorithmus}, wenn alle Kanten von $s'$ saturiert sind ist der Fluss in $G$ gültig. $x$ beschränkt den Fluss in $G$ (Binary-Search für minflow, $\infty$ sonst).
\item \textbf{\textsc{Johnson}s Reweighting Algorithm:}
Initialisiere alle Entfernungen mit \texttt{d[i] = 0}. Berechne mit \textsc{Bellmann-Ford} kürzeste Entfernungen.
Falls es einen negativen Zyklus gibt abrrechen.
|
