Re: [Tcllib-devel] FordFulkerson

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

Lars Hellström wrote:
> 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.

Thanks for the explanation. Looking at the rev 33 code it seems that it uses 
dijktra with the capacity weights, so not shortest path by hop, but by 
remaining capacity.

Might make sense to modify dijkstra to be able to ignore any weights

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

Yes. See also my comments then Michal asked me about node weights. I asked him 
to try to use the standard node attributes for that, instead of distinct node 
weights. For comparison, and later (aater GSoC) to possibly change the existing 
code over to regular arc attributes for weights etc.

Andreas.