Hungarian algorithm: Difference between revisions

Revision as of 15:14, 20 April 2025

Revision as of 15:19, 20 April 2025

Line 321:

<syntaxhighlight lang="cpp" line="1">

template <typename T>

template <class T> vectorVector<T> hungarian(const vectorVector<vectorVector<T>>& &C) {

const int J = (static_cast<int)size>(C), W = (int).size(C[0]));

const int W = static_cast<int>(C[0].size());

assert(J <= W);

// job[w] = job assigned to w-th worker, or -1 if no job assigned

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

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

vectorVector<T> h(W); // Johnson potentials

vectorVector<T> answers;

T ans_curansCur = 0;

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

// assign j_curjCur-th job using Dijkstra with potentials

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

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

job[w_curwCur] = j_cur;

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

dist[W] = 0;

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

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

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

T min_distminDist = inf;

vis[w_curwCur] = true;

int w_nextwNext = -1; // next unvisited worker with minimum distance

// consider extending shortest path by w_curwCur -> job[w_curwCur] -> w

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

if (!vis[w]) {

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

T edge = C[job[w_curwCur]][w] - h[w];

if (w_curwCur != W) {

edge -= C[job[w_curwCur]][w_curwCur] - h[w_curwCur];

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

}

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

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

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

wNext = w;

}

}

Line 359 ⟶ 363:

}

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

ckmin(dist[w], dist[w_curwCur]);

h[w] += dist[w];

}

ans_cur += h[w_curwCur];

for (int w; w_curwCur != W; w_curwCur = w)
job[w_curwCur] = job[w = prv[w_curwCur]];

answers.push_back(ans_curansCur);

}

return answers;