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

# | User | Rating |
---|---|---|

1 | Benq | 3796 |

2 | tourist | 3722 |

3 | Radewoosh | 3719 |

4 | ecnerwala | 3578 |

5 | ksun48 | 3462 |

6 | Um_nik | 3456 |

7 | maroonrk | 3445 |

8 | jiangly | 3431 |

9 | Petr | 3370 |

10 | scott_wu | 3350 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 207 |

2 | awoo | 186 |

3 | rng_58 | 184 |

4 | Errichto | 182 |

5 | SecondThread | 177 |

5 | Radewoosh | 177 |

7 | -is-this-fft- | 176 |

7 | maroonrk | 176 |

9 | Um_nik | 173 |

10 | antontrygubO_o | 171 |

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

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/16/2021 05:20:46 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Auto comment: topic has been updated by u1804011 (previous revision, new revision, compare).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.

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

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