Re: [Tcllib-devel] FordFulkerson

[Lars H. <Lar...@re...>]

Andreas Kupries skrev:
> Lars Hellström wrote:
>> Using [dijkstra] for computing the augmenting path /probably/ means it 
>> will be a shortest path (though it depends on how weights are assigned 
>> in $residualG),
> 
> Can you explain how the weights have to be assigned in the residualG to 
> not make this a shortest path ?

If the weights are taken to be the residual capacities, then in a 
$residualG of

       1        2
   u -----> v -----> w
   |                 A
   |        8        |
   +-----------------+,

[dijkstra] will pick u->v->w as shortest path from u to w, even though 
the shortest path in the sense relevant here (fewest number of edges) 
is u->w. All weights equal to 1 makes the two concepts equal.

BTW, this is why I'm skeptical against the distiguished weight property 
of [struct::graph]s: sometimes weight means cost, other times it means 
capacity, so mixing algorithms that apply one interpretation with 
algorithms that apply the other is going to be awkward.

Lars Hellström