Re: [Tcllib-devel] FordFulkerson

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

Michał Antoniewski wrote:
>         ( Bellman-Ford's is worser to use in that case than Dijkstra ).
>         However,
>         I've found some info saying that there is algorithm (path
>         finding), which
>         suits best for flow problems - it's faster than Dijkstra for
>         rare networks
> 
> 
>     Do you mean _sparse_ networks?
> Yes, sorry. Sometimes translating literally is dangerous :) 

Quite.


>     No, the literature I have just discusses BFS vs. DFS for finding
>     augmenting paths. I believe most work on faster max-flow algorithms
>     rather focuses on doing something other than augmenting paths, e.g.
>     blocking flows (Dinic) or push&relabel (Goldberg--Tarjan).

> I found some more info on that. Firstly, about Dijkstra, it can be used 
> in flow problems, but it's needed to do some changes, like when weights 
> are negative, adding the same value to all weights, just to get all 
> positive weights in network (so, the differences between them are 
> constant ). Also, I found out that this PDM algorithm I mentioned is 
> Moore's-Bellman's-d'Esopo-Papego algorithm for finding paths between two 
> nodes, but negative weights are possible. When, I looked at pseudocode 
> it turned out to be....BFS (weighted) :) :)  This weird name PDM made 
> some confusion... So generally, BFS is better than Dijkstra ( however, 
> it can't be stopped like Dijkstra, when found certain path and must go 

Note that our dijkstra implementation cannot stop either. Maybe a cut-down 
implementation is needed to just find a single path A -> B, which stops as 
early as possible ?

> through all paths ), so I guess it should be placed in implementation 

I guess you meant	"in _its own_ implementation"

> instead of Dijkstra's.


> Oh, that's interesting. I didn't know before those CS and Orlin's 
> algorithms. I've decided to choose Busacker-Gowen (or SSP) to add in my 
> application's timeline, as it was AFAIK the most popular algorithm for 
> that problem and also well known to me.

Andreas.