Flow Network
Back to Problem Solutions forum
I'm using a prepared Ford Fulkerson algorithm (from my own algo-library), it forks fine for coursera tasks, but it fails for this problem.
I'll try check java solution tomorrow.
Feel free to write about any suspicions you may have!
I'm not quite sure about my own code because I have no chance to test it on larger independent datasets :(
I solved it by making bidirectional edges
v1->v2:w
v2->v1:w
So by searching augmenting paths it needs to doubling edge, so for one line from condition it maked 4 (four) edges at FlowNetwork.
For some cases my solution differs with checker. I'll try to make more analysis later.
Yes, edges are bi-directional (I hope it was mentioned)... But I think for augmented path you need only pair of edges, not four. I.e.:
G: (graph description)
v1->v2:w
v2->v1:w
F: (flow description)
v1->v2:x
v2->v1:-x
Hope we'll be able to find out the truth later :)
I solved it from scratch with a BFS. When the end point is found, I search the minimum flow for the way I found.
Then I substract it to the adjacency matrix (and a full route is removed) and add it to the flow matrix in the right way and remove it on the opposite way.
I was surprised that it worked.
>I was surprised that it worked.
Yes, it is interesting! I suspect your solution may fail if there are edges for which flow direction should be reverted by some of later paths (because you subtract flows from adjacency matrix and could not restore them if necessary).
I've added such example (second) to problem statement - but I'm afraid it is hard to create randomized input data set with such a nice property... Probably your solution will not work for this case...