Hungarian algorithm: Difference between revisions

Revision as of 05:33, 14 May 2023

Revision as of 05:57, 14 May 2023

Line 281:

}}</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

to optimize this algorithm to run in <math>O(JM+J^2\log W)</math> time by using a Fibonacci heap to determine

<math>w_{\text{next}}</math> instead of iterating over all <math>W</math> workers to find the one with minimum distance (alluded to [[Assignment_problem#Balanced_assignment|here]]).

Line 292:

// note: a W-th worker was added for convenience

vector<int> job(W + 1, -1);

vector<T> h(W + 1); // Johnson potentials

vector<T> answers;

T ans_cur = 0;

Line 312:

if (!vis[w]) {

// sum of reduced edge weights w_cur -> job[w_cur] -> w

const T edge = C[job[w_cur]][w] - Ch[job[w_curw]][w_cur] -;

if (w_cur != W) h[w] + h[w_cur];{

if (w_cur ! edge -= W)C[job[w_cur]][w_cur] - h[w_cur];

assert(edge >= 0); // consequence of Johnson potentials

}

if (ckmin(dist[w], dist[w_cur] + edge)) prv[w] = w_cur;

if (ckmin(min_dist, dist[w])) w_next = w;