2
$\begingroup$

I'm doing a min cost assignation problem to assign doctors to their working days for a hospital.

After correctly getting the max flow with Ford-Fulkerson algorithm, I would like to use the cycle canceling algorithm to minimze the flow's cost. I'm basically using the Bellman-Ford algorithm from the sink of the residual graph with the max flow.

The problem is that Bellman-Ford gives me one negative weight cycle (the one that reduces more the cost), and in a given example, such cycle has a bottleneck capacity of 0, so I cannot send flow around it. However in the very same example, other negative weight cycles exist with a bottleneck capacity strictly greater than 0. Sending the bottleneck flow among these cycles would certainly reduce the cost of my assignment, nevertheless the Bellman-Ford implementation does not seem to be capable of yielding such cycles.

How might I get all the graph's negative cycles, to finally get the min cost assignation?

For this university project, the algorithm's performance is not relevant.

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ Note that there can, in general, be exponentially many negative-weight cycles (for a trivial example, take a complete graph with every edge having negative weight) so a polynomial-time algorithm is impossible. $\endgroup$ – David Richerby Dec 7 '14 at 10:35
  • $\begingroup$ I know the performance is going to be low, however this corresponds to the university course 'programming projects', so they told us not to worry about it, as that is not the focus of the subject. $\endgroup$ – Martí Bosch Dec 7 '14 at 10:56
  • 1
    $\begingroup$ If costs are not an issue, just inspect all cycles. Note furthermore that min-cost flows are a thing in the literature. $\endgroup$ – Raphael♦ Dec 7 '14 at 11:08
  • $\begingroup$ @Raphael if by 'cost' you mean 'complexity of the algorithm', yes, they are not an issue. However isn't there a way to get only the negative cycles using the Bellman-Ford algorithm? After the first |V|-1 iterations, if some edge has distance(destination) > distance(source) + cost(edge), this means that is a negative cycle. What I'm trying to do is: after I've found this negative cycle, keep looking until I find all of them. Can I do that with Bellman-Ford? Thanks! $\endgroup$ – Martí Bosch Dec 7 '14 at 12:03
  • $\begingroup$ What does the invariant resp. the definition of every "cell" content of BF tell you? $\endgroup$ – Raphael♦ Dec 7 '14 at 12:15
1
$\begingroup$

You can use a brute force over all sequences of vertices, check if the permutation represents a negative cycle, and if so- print the cycle. This is not an efficient algorithm (runs at $O(n^{n+1})$), but a simple one

Suppose all vertices are denoted by $1,2,\ldots,n$. We denote by $C[i]$ the $i^{th}$ node in the cycle, for $i=1,2,\ldots,k$, where $3 \leq k\leq n-1$ is the size of the cycle.

A pseudo code of the algorithm goes as follows:

  1. Let $k\gets 3$

  2. If $k==n$, then terminate the algorithm.

  3. Let $C[i]\gets 1$ for $i=1,2,\ldots,k$

  4. Check if $C=(C[1],C[2],\ldots,C[k],C[1])$ is a negative cycle in the graph. If so- print $C$

  5. If $C[1]=C[2]=\ldots=C[k]=n$, then $k \gets k+1$ and go to step 2.

  6. Otherwise, select $C[j]=\min_i C[i]$ (if there are multiple $j$-s with the minimal value, select the one with the minimal index), assign $C[j]\gets C[j]+1$ and go to step 4.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.