Re: [Tcllib-devel] FordFulkerson

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

Michał Antoniewski skrev:
>  Hello.
> 
> About flow problems:
> - Edmond's Karp algorithm, like Lars has written, is indeed extension of
> Ford's Fulkerson. The difference is as it was said, in Edmond's Karp we
> search for shortest paths between s and t. Just to mention, those shortest
> paths are chosen considering the smallest amount of edges between s and t,
> not throughputs. So, it's like running Dijkstra on residual graph, with all
> weights at edges set to 1, just for that one operation. After some thinking,
> I don't see any way to omit using Dijkstra or any other path finding method

Note that a basic breadth-first-search would be sufficient here (a 
tragedy of the 60's is that DFS was easier to implement than BFS; had 
it been the other way round, it's probable that Ford and Fulkerson 
would have ended up with Edmonds--Karp from the start).

> ( 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?

> and for typical flow problems even for complete networks. It was called PDM,
> so I have to review it and find some more info about it to say more about is
> it worth implementing it....
> 
> Maybe Lars knows anything about it? I would guess, it can be some improved
> version of e.g. Dijkstra, adapted for flow problems.

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

> So, I think I'm going to extend Ford-Fulkerson into Edmond's Karp (
> actually, it's already done ).
> 
> - min cost flow problems - actually, we've got one algorithm in timeline for
> that: Busacker-Gowen ( already implemented,just have to do some more tests )

Also known as "successive shortest path algorithm", it seems (the 
underlying theorem appears independently in at least three papers, only 
one of which is by Busacker and Gowen). If so, then I'm not surprised, 
as this algorithm appears to be very similar to Ford--Fulkerson 
(including the unfortunate dependence on capacities in the running 
time). Should indeed be a rather minor modification of what you've 
already presented.

There appears to be a catch, however: I see a mention that one cannot 
at all steps use Dijkstra to find the shortest paths, as there may be 
negative weights (costs) on edges.

> - another extension is Dinic method combined with Malhotra-Kumar-Maheshwari
> algorithm ( which finds blocking flow ). It's another way for finding max
> flow in flow networks. As far as I know, there is also Dinic's algorithm for
> finding blocking flows, so actually, that also can be chosen... Both
> algorithms (Dinic and Malhotra-Kumar-Maheshwari) are now in timeline, but

Both Dinic and Malhotra--Kumar--Maheshwari appear to be max-flow 
algorithms, AFAICT.

For min-cost-flow, the literature I have at hand rather suggests the 
capacity scaling algorithm (by Edmonds and Karp) or Orlin's algorithm, 
both of which are polynomial. A catch is however that at least the 
descriptions I have for these are for the uncapacitated min-cost-flow 
problem. Min-cost-flow with capacities can be reduced to min-cost-flow 
without capacities, but there is an overhead for doing so. The 
complexities appear to be

          Uncapacitated       Capacitated
SSP      O(mn+B(n^2+m))      O(mn+B(n^2+m))
CS       O(n(n^2+m)\log B)   O(m(n^2+m)\log B)?
Orlin    O(n(n^2+m)\log m)   O(m(n^2+m)\log m)
MMCC     O(m^3 n^2 \log n)   O(m^3 n^2 \log n)

Here, n=number of vertics, m=number of edges, and B is the sum over all 
vertices of the absolute value of the net flow at that vertex. SSP = 
Successive Shortest Path (Busacker--Gowen) Algorithm, CS = Capacity 
Scaling Algorithm, and MMCC = Minimum Mean Cycle-Cancelling Algorithm.

Unfortunately, there is no clear winner.


Lars Hellström