From: Michał A. <ant...@gm...> - 2009-07-13 16:56:38
|
2009/7/12 Lars Hellström <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). > Actually, next step in timeline will be spanning tree algorithms, like spanning tree with minimum diameter which uses BFS, so BFS is in timeline anyway. > > > ( 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 :) > > > 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). > 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 through all paths ), so I guess it should be placed in implementation instead of Dijkstra's. Next algorithm in timeline considering flow problems is Dinic and 3 Hindu algorithm, with blocking flows etc. Actually, we were talking with Andreas about replacing it with some new problems ( Set Cover, Shortest Super String ), but in that case maybe, it's worth not to erase it from timeline and maybe replacing with Set Cover another problem (if any)? > 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. > Yes, Dijkstra can't be used, if we don't modify it a bit ( like I said above ), what makes it also more costly. Busacker-Gowen and Ford-Fulkerson are based on the same concept, so there indeed are similarities, but still needed to be examined in new problem definition. - 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 > > 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. Best Regards, Michał Antoniewski |