Блог пользователя u1804011

Автор u1804011, история, 3 года назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится -15 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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