Re: [Tcllib-devel] Busacker-Gowen

[Michał A. <ant...@gm...>]

So, Busacker and Gowen, a little description:

Generally, the problem concerns finding the max possible flow (but not
greater than 'd', which we give at input ) but now input network not only
has throughputs but also each edge has it's cost. So, we are seaching for
max flow with a minimum cost from source to sink.

Algorithm goes like this:
- we search for shortest path between s and t ( considering edge costs )
- we compute maximum value of throughput that can be send by the path
- if adding such througput exceeds 'd' (input value of flow we desired) we
add as much as possible (so the desired flow value 'd' is reached)
- transform network into Augmenting Network
- repeat from the top.
- procedure ends when there is no path, or 'd' is reached.

Everything is described in the code.

Best Regards,
Michał Antoniewski