Mercurial > hgrepos > Python > libs > pygments-lexer-pseudocode2

annotate docs/algorithm-ford-fulkerson.pseudocode @ 114:be50fe0687d6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
The \CALL command
author Franz Glasner <fzglas.hg@dom66.de>
date Wed, 06 May 2026 01:10:11 +0200
parents 6cebd3e7bc97
children 9bfd87544902
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
107
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
1 // -*- coding: utf-8; indent-tabs-mode: nil -*-
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
2 \ALGORITHM{Ford–Fulkerson} \WITH
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
3 \INPUTS{Given a network \expr{G = (V, E)} with flow capacity \expr{c}, a source node \expr{s}, and a sink node \expr{t}}
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
4 \OUTPUT{Compute a flow \expr{f} from \expr{s} to \expr{t} of maximum value}
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
5 \IS
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
6 \TEXT{1. \expr{f(u, v) <- 0} for all edges \expr{(u, v)}
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
7
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
8 2. While there is a path \expr{p} from \expr{s} to \expr{t} in \expr{G_f},
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
9 such that \expr{c_f(u, v) > 0} for all edges \expr{(u, v) ∈ p}:
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
10
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
11 1. Find \expr{c_f(p) = min{c_f(u, v): (u, v) ∈ p\}}
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
12
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
13 2. For each edge \expr{(u, v) ∈ p}
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
14
108
6cebd3e7bc97 Also allow \REM within a \TEXT{}
Franz Glasner <fzglas.hg@dom66.de>
parents: 107
diff changeset
15 1. \expr{f(u, v) <- f(u, v) + c_f(p)} \rem Send flow along the path
107
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
16
108
6cebd3e7bc97 Also allow \REM within a \TEXT{}
Franz Glasner <fzglas.hg@dom66.de>
parents: 107
diff changeset
17 2. \expr{f(v, u) <- f(v, u) - c_f(p)} \rem The flow might be "returned" later
6cebd3e7bc97 Also allow \REM within a \TEXT{}
Franz Glasner <fzglas.hg@dom66.de>
parents: 107
diff changeset
18 }
107
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
19 \END ALGORITHM {Ford–Fulkerson}