Hungarian algorithm: Difference between revisions

Revision as of 09:49, 11 July 2023

Revision as of 08:50, 5 September 2023

Line 272:

| website = Algorithms for Competitive Programming

| access-date = May 14, 2023

}}</ref> <ref>{{cite web

| url = https://cp-algorithms.com/graph/Assignment-problem-min-flow.html

| title = Solving assignment problem using min-cost-flow

Line 279:

| website = Algorithms for Competitive Programming

| access-date = May 14, 2023

}}</ref> where the reweighting technique from [[Johnson's_algorithm|Johnson's algorithm]] is used to find the shortest paths.

The implementation from the previous section is rewritten below in such a way as to emphasize this

connection; it can be checked that the potentials <math>h</math> for workers <math>0\dots W-1</math> are equal to the potentials <math>y</math> from the previous solution up to a constant offset. When the graph is sparse (there are only <math>M</math> allowed job, worker pairs), it is possible