Re: [Tcllib-devel] Busacker-Gowen

[Andreas K. <and...@ac...>]

Michał Antoniewski wrote:
> 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.

And here is another example to fuel Lars's objection against distinct arc 
weights. We have arc capacaties and costs, both of which are some sort of 
weight, for the different parts of the algorithm

> 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.

Ok.

Andreas.