Hungarian algorithm: Difference between revisions

Revision as of 15:20, 20 April 2025

Revision as of 16:50, 20 April 2025

Line 154:

using Pair = std::pair;

using Vector = std::vector;

template <typename T>

using NumericLimits = std::numeric_limits<T>;

/**

Line 195 ⟶ 198:

// -yt[W] will equal the sum of all deltas

Vector<T> answers;

const T inf = std::numeric_limitsNumericLimits<T>::max();

for (int jCur = 0; jCur < J; ++jCur) { // assign jCur-th job

int wCur = W;

Line 201 ⟶ 204:

// min reduced cost over edges from Z to worker w

Vector<T> minTo(W + 1, inf);

Vector<int> prvprev(W + 1, -1); // previous worker on alternating path

Vector<bool> inZ(W + 1); // whether worker is in Z

while (job[wCur] != -1) { // runs at most jCur + 1 times

Line 211 ⟶ 214:

if (!inZ[w]) {

if (ckmin(minTo[w], C[j][w] - ys[j] - yt[w]))

prvprev[w] = wCur;

if (ckmin(delta, minTo[w]))

wNext = w;

Line 231 ⟶ 234:

// update assignments along alternating path

for (int w; wCur != W; wCur = w)

job[wCur] = job[w = prvprev[wCur]];

answers.push_back(-yt[W]);

}

Line 332 ⟶ 335:

Vector<T> answers;

T ansCur = 0;

const T inf = std::numeric_limitsNumericLimits<T>::max();

// assign jCur-th job using Dijkstra with potentials

for (int jCur = 0; jCur < J; ++jCur) {

int wCur = W; // unvisited worker with minimum distance

job[wCur] = j_curjCur;

Vector<T> dist(W + 1, inf); // Johnson-reduced distances

dist[W] = 0;

Vector<bool> vis(W + 1); // whether visited yet

Vector<int> prvprev(W + 1, -1); // previous worker on shortest path

while (job[wCur] != -1) { // Dijkstra step: pop min worker from heap

T minDist = inf;

Line 355 ⟶ 358:

}

if (ckmin(dist[w], dist[wCur] + edge))

prvprev[w] = wCur;

if (ckmin(minDist, dist[w]))

wNext = w;

}

}

w_curwCur = w_nextwNext;

}

for (int w = 0; w < W; ++w) { // update potentials

Line 368 ⟶ 371:

ans_cur += h[wCur];

for (int w; wCur != W; wCur = w)

job[wCur] = job[w = prvprev[wCur]];

answers.push_back(ansCur);

}