When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

u1804011's blog

By u1804011, history, 3 years ago, In English

Can we use dijkstra algorithm to find maximum bipartite matching with minimum cost? If we can,how??

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Not directly, but it is possible with some modifications.

Finding the shortest augmenting path in every iteration works. The issue is that Djikstra cannot handle negative weight edges.

However, this can be dealt with, by maintaining potentials $$$P(v)$$$ for every vertex $$$v$$$, and using edge costs $$$C(u, v) = c(u, v) + P(u) - P(v)$$$. If $$$P(v)$$$ is the shortest distance from the source $$$s$$$ to $$$v$$$, then $$$P(v) \leq P(u) + c(u, v)$$$, thus all modified edge weights are nonnegative (as long as there are no negative weight cycles, which there won't be, in this case).

With the modified costs, the distance between $$$s$$$ and $$$t$$$ is $$$D(s, t) = d(s, t) + P(s) - P(t)$$$, thus the shortest path with negative weights is still the shortest path with the modified weights.

To maintain the potentials, after every augment, since you used djikstra, you have the distances $$$P'$$$ from the source. Using $$$P' + P$$$ as potentials makes all edges nonnegative.

For edges $$$(u, v)$$$ not on the augmenting path, \begin{equation*} C'(u, v) = c(u, v) + (P'(u) + P(u)) — (P'(v) + P'(v)) = C(u, v) + P'(u) — P'(v) \geq 0 \end{equation*} since $$$P'(v) \leq P'(u) + C(u, v)$$$.

For edges $$$(u, v)$$$ on the augmenting path, since the augmenting path is a shortest path, we have $$$P'(u) + C(u, v) = P'(v)$$$. Thus \begin{equation*} C'(u, v) = c(u, v) + (P'(u) + P(u)) — (P'(v) + P(v)) = C(u, v) + P'(u) — P'(v) \end{equation*} and \begin{equation*} C'(v, u) = -c(u, v) + (P'(v) + P(v)) — (P'(u) + P(u)) = -(C(u, v) + P'(u) — P'(v)) = 0 \end{equation*}

The remaining problem is that the potentials can get too large. To fix this, add a temporary vertex with a edge of cost $$$-P(u)$$$ to $$$u$$$, and add to the potentials the distances $$$P'$$$ from the temporary vertex. Since \begin{equation*} P'(v) = \min_u -P(u) + (d(u, v) + P(u) — P(v)) \end{equation*} we have \begin{equation*} -(n-1) \max_{u, v} c(u, v) \leq P'(v) + P(v) \leq 0 \end{equation*}

This gives a $$$\mathcal{O}(F m \log n)$$$ algorithm for min-cost max-flow, where $$$F$$$ is the total flow.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    Is this code correct?? I only iterate dijkstra as long as augmanting path exist. https://ideone.com/iP5Kp1

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      That does none of what I said...

      Try for example this input. The correct answer is 46, you give 50.

      Test you get WA on