Hungarian algorithm - Revision history

24.50.56.74: /* Implementation in C++ */

2025-05-23T15:38:13Z

Implementation in C++

← Previous revision		Revision as of 15:38, 23 May 2025
Line 152:		Line 152:
	import std;		import std;

			template <typename T, typename U>
⚫	using ~~Pair~~ = std::~~pair~~;
	using ~~Vector~~ = std::~~vector~~;		using Pair = std::pair<T, U>;
			template <typename T>
		⚫	using Vector = std::vector<T>;

	template <typename T>		template <typename T>

24.50.56.74: /* Implementation in C++ */

2025-05-23T15:37:27Z

Implementation in C++

← Previous revision		Revision as of 15:37, 23 May 2025
Line 148:		Line 148:
	*/		*/

	~~#include~~ <cassert>		import <cassert>;

	import std;		import std;

89.158.3.144: changed unmarked to uncovered

2025-05-02T17:31:25Z

changed unmarked to uncovered

← Previous revision		Revision as of 17:31, 2 May 2025
Line 568:		Line 568:
	If the number of starred zeros is {{mvar\|n}} (or in the general case <math>min(n,m)</math>, where {{mvar\|n}} is the number of people and {{mvar\|m}} is the number of jobs), the algorithm terminates. See the [[#Result\|Result]] subsection below on how to interpret the results.		If the number of starred zeros is {{mvar\|n}} (or in the general case <math>min(n,m)</math>, where {{mvar\|n}} is the number of people and {{mvar\|m}} is the number of jobs), the algorithm terminates. See the [[#Result\|Result]] subsection below on how to interpret the results.

	Otherwise, find the lowest uncovered value. Subtract this from every ~~unmarked~~ element and add it to every element covered by two lines. Go back to step 4.		Otherwise, find the lowest uncovered value. Subtract this from every uncovered element and add it to every element covered by two lines. Go back to step 4.

	This is equivalent to subtracting a number from all rows which are not covered and adding the same number to all columns which are covered. These operations do not change optimal assignments.		This is equivalent to subtracting a number from all rows which are not covered and adding the same number to all columns which are covered. These operations do not change optimal assignments.

2620:101:F000:7C0:0:0:0:25CF at 16:50, 20 April 2025

2025-04-20T16:50:29Z

← Previous revision		Revision as of 16:50, 20 April 2025
Line 154:		Line 154:
	using Pair = std::pair;		using Pair = std::pair;
	using Vector = std::vector;		using Vector = std::vector;

			template <typename T>
			using NumericLimits = std::numeric_limits<T>;

	/**		/**
Line 195:		Line 198:
	// -yt[W] will equal the sum of all deltas		// -yt[W] will equal the sum of all deltas
	Vector<T> answers;		Vector<T> answers;
	const T inf = ~~std::numeric_limits~~<T>::max();		const T inf = NumericLimits<T>::max();
	for (int jCur = 0; jCur < J; ++jCur) { // assign jCur-th job		for (int jCur = 0; jCur < J; ++jCur) { // assign jCur-th job
	int wCur = W;		int wCur = W;
Line 201:		Line 204:
	// min reduced cost over edges from Z to worker w		// min reduced cost over edges from Z to worker w
	Vector<T> minTo(W + 1, inf);		Vector<T> minTo(W + 1, inf);
	Vector<int> ~~prv~~(W + 1, -1); // previous worker on alternating path		Vector<int> prev(W + 1, -1); // previous worker on alternating path
	Vector<bool> inZ(W + 1); // whether worker is in Z		Vector<bool> inZ(W + 1); // whether worker is in Z
	while (job[wCur] != -1) { // runs at most jCur + 1 times		while (job[wCur] != -1) { // runs at most jCur + 1 times
Line 211:		Line 214:
	if (!inZ[w]) {		if (!inZ[w]) {
	if (ckmin(minTo[w], C[j][w] - ys[j] - yt[w]))		if (ckmin(minTo[w], C[j][w] - ys[j] - yt[w]))
	~~prv~~[w] = wCur;		prev[w] = wCur;
	if (ckmin(delta, minTo[w]))		if (ckmin(delta, minTo[w]))
	wNext = w;		wNext = w;
Line 231:		Line 234:
	// update assignments along alternating path		// update assignments along alternating path
	for (int w; wCur != W; wCur = w)		for (int w; wCur != W; wCur = w)
	job[wCur] = job[w = ~~prv~~[wCur]];		job[wCur] = job[w = prev[wCur]];
	answers.push_back(-yt[W]);		answers.push_back(-yt[W]);
	}		}
Line 332:		Line 335:
	Vector<T> answers;		Vector<T> answers;
	T ansCur = 0;		T ansCur = 0;
	const T inf = ~~std::numeric_limits~~<T>::max();		const T inf = NumericLimits<T>::max();
	// assign jCur-th job using Dijkstra with potentials		// assign jCur-th job using Dijkstra with potentials
	for (int jCur = 0; jCur < J; ++jCur) {		for (int jCur = 0; jCur < J; ++jCur) {
	int wCur = W; // unvisited worker with minimum distance		int wCur = W; // unvisited worker with minimum distance
	job[wCur] = ~~j_cur~~;		job[wCur] = jCur;
	Vector<T> dist(W + 1, inf); // Johnson-reduced distances		Vector<T> dist(W + 1, inf); // Johnson-reduced distances
	dist[W] = 0;		dist[W] = 0;
	Vector<bool> vis(W + 1); // whether visited yet		Vector<bool> vis(W + 1); // whether visited yet
	Vector<int> ~~prv~~(W + 1, -1); // previous worker on shortest path		Vector<int> prev(W + 1, -1); // previous worker on shortest path
	while (job[wCur] != -1) { // Dijkstra step: pop min worker from heap		while (job[wCur] != -1) { // Dijkstra step: pop min worker from heap
	T minDist = inf;		T minDist = inf;
Line 355:		Line 358:
	}		}
	if (ckmin(dist[w], dist[wCur] + edge))		if (ckmin(dist[w], dist[wCur] + edge))
	~~prv~~[w] = wCur;		prev[w] = wCur;
	if (ckmin(minDist, dist[w]))		if (ckmin(minDist, dist[w]))
	wNext = w;		wNext = w;
	}		}
	}		}
	~~w_cur~~ = ~~w_next~~;		wCur = wNext;
	}		}
	for (int w = 0; w < W; ++w) { // update potentials		for (int w = 0; w < W; ++w) { // update potentials
Line 368:		Line 371:
	ans_cur += h[wCur];		ans_cur += h[wCur];
	for (int w; wCur != W; wCur = w)		for (int w; wCur != W; wCur = w)
	job[wCur] = job[w = ~~prv~~[wCur]];		job[wCur] = job[w = prev[wCur]];
	answers.push_back(ansCur);		answers.push_back(ansCur);
	}		}

216.181.201.183: /* Implementation in C++ */

2025-04-20T15:20:07Z

Implementation in C++

← Previous revision		Revision as of 15:20, 20 April 2025
Line 268:		Line 268:
	Vector<Pair<int, int>> bottles(N);		Vector<Pair<int, int>> bottles(N);
	Vector<Pair<int, int>> couriers(M);		Vector<Pair<int, int>> couriers(M);
	for (const Pair<int, int>& b : bottles)		for (const Pair<int, int>& b: bottles)
	std::cin >> b.first >> b.second;		std::cin >> b.first >> b.second;
	for (const Pair<int, int>& c : couriers)		for (const Pair<int, int>& c: couriers)
	std::cin >> c.first >> c.second;		std::cin >> c.first >> c.second;
	Pair<int, int> rest;		Pair<int, int> rest;

216.181.201.183: /* Connection to successive shortest paths */

2025-04-20T15:19:11Z

Connection to successive shortest paths

← Previous revision		Revision as of 15:19, 20 April 2025
Line 321:		Line 321:

	<syntaxhighlight lang="cpp" line="1">		<syntaxhighlight lang="cpp" line="1">
			template <typename T>
	~~template <class T> vector~~<T> hungarian(const ~~vector~~<~~vector~~<T>> &C) {		Vector<T> hungarian(const Vector<Vector<T>>& C) {
	const int J = (int~~)size~~(C~~), W = (int)~~size(~~C[0]~~);		const int J = static_cast<int>(C.size());
			const int W = static_cast<int>(C[0].size());
	assert(J <= W);		assert(J <= W);
	// job[w] = job assigned to w-th worker, or -1 if no job assigned		// job[w] = job assigned to w-th worker, or -1 if no job assigned
	// note: a W-th worker was added for convenience		// note: a W-th worker was added for convenience
	~~vector~~<int> job(W + 1, -1);		Vector<int> job(W + 1, -1);
	~~vector~~<T> h(W); // Johnson potentials		Vector<T> h(W); // Johnson potentials
	~~vector~~<T> answers;		Vector<T> answers;
	T ~~ans_cur~~ = 0;		T ansCur = 0;
	const T inf = numeric_limits<T>::max();		const T inf = std::numeric_limits<T>::max();
	// assign ~~j_cur~~-th job using Dijkstra with potentials		// assign jCur-th job using Dijkstra with potentials
	for (int ~~j_cur~~ = 0; ~~j_cur~~ < J; ++~~j_cur~~) {		for (int jCur = 0; jCur < J; ++jCur) {
	int ~~w_cur~~ = W; // unvisited worker with minimum distance		int wCur = W; // unvisited worker with minimum distance
	job[~~w_cur~~] = j_cur;		job[wCur] = j_cur;
	~~vector~~<T> dist(W + 1, inf); // Johnson-reduced distances		Vector<T> dist(W + 1, inf); // Johnson-reduced distances
	dist[W] = 0;		dist[W] = 0;
	~~vector~~<bool> vis(W + 1); // whether visited yet		Vector<bool> vis(W + 1); // whether visited yet
	~~vector~~<int> prv(W + 1, -1); // previous worker on shortest path		Vector<int> prv(W + 1, -1); // previous worker on shortest path
	while (job[~~w_cur~~] != -1) { // Dijkstra step: pop min worker from heap		while (job[wCur] != -1) { // Dijkstra step: pop min worker from heap
	T ~~min_dist~~ = inf;		T minDist = inf;
	vis[~~w_cur~~] = true;		vis[wCur] = true;
	int ~~w_next~~ = -1; // next unvisited worker with minimum distance		int wNext = -1; // next unvisited worker with minimum distance
	// consider extending shortest path by ~~w_cur~~ -> job[~~w_cur~~] -> w		// consider extending shortest path by wCur -> job[wCur] -> w
	for (int w = 0; w < W; ++w) {		for (int w = 0; w < W; ++w) {
	if (!vis[w]) {		if (!vis[w]) {
	// sum of reduced edge weights ~~w_cur~~ -> job[~~w_cur~~] -> w		// sum of reduced edge weights wCur -> job[wCur] -> w
	T edge = C[job[~~w_cur~~]][w] - h[w];		T edge = C[job[wCur]][w] - h[w];
	if (~~w_cur~~ != W) {		if (wCur != W) {
	edge -= C[job[~~w_cur~~]][~~w_cur~~] - h[~~w_cur~~];		edge -= C[job[wCur]][wCur] - h[wCur];
	assert(edge >= 0); // consequence of Johnson potentials		assert(edge >= 0); // consequence of Johnson potentials
	}		}
	if (ckmin(dist[w], dist[~~w_cur~~] + edge)) ~~prv[w] = w_cur;~~		if (ckmin(dist[w], dist[wCur] + edge))
	if ~~(ckmin(min_dist,~~ ~~dist~~[w]~~)) w_next~~ = w;		prv[w] = wCur;
			if (ckmin(minDist, dist[w]))
			wNext = w;
	}		}
	}		}
Line 359:		Line 363:
	}		}
	for (int w = 0; w < W; ++w) { // update potentials		for (int w = 0; w < W; ++w) { // update potentials
	ckmin(dist[w], dist[~~w_cur~~]);		ckmin(dist[w], dist[wCur]);
	h[w] += dist[w];		h[w] += dist[w];
	}		}
	ans_cur += h[~~w_cur~~];		ans_cur += h[wCur];
	for (int w; ~~w_cur~~ != W; ~~w_cur~~ = w) job[~~w_cur~~] = job[w = prv[~~w_cur~~]];		for (int w; wCur != W; wCur = w)
			job[wCur] = job[w = prv[wCur]];
	answers.push_back(~~ans_cur~~);		answers.push_back(ansCur);
	}		}
	return answers;		return answers;

216.181.201.183: /* Implementation in C++ */

2025-04-20T15:14:29Z

Implementation in C++

← Previous revision		Revision as of 15:14, 20 April 2025
Line 156:		Line 156:

	/**		/**
			* @brief Checks if b < a
			*
	* Sets a = min(a, b)		* Sets a = min(a, b)
			* @param a The first parameter to check
			* @param b The second parameter to check
			* @tparam The type to perform the check on
	* @return true if b < a		* @return true if b < a
	*/		*/
	template <typename T>		template <typename T>
	constexpr bool ckmin(T& a, const T& b) {		constexpr bool ckmin(T& a, const T& b) {
	return b < a ? a = b, 1 : 0;		return b < a ? a = b, true : false;
	}		}

	/**		/**
			* @brief Performs the Hungarian algorithm.
			*
	* Given J jobs and W workers (J <= W), computes the minimum cost to assign each		* Given J jobs and W workers (J <= W), computes the minimum cost to assign each
	* prefix of jobs to distinct workers.		* prefix of jobs to distinct workers.
Line 195:		Line 202:
	Vector<T> minTo(W + 1, inf);		Vector<T> minTo(W + 1, inf);
	Vector<int> prv(W + 1, -1); // previous worker on alternating path		Vector<int> prv(W + 1, -1); // previous worker on alternating path
	Vector<bool> inZ(W + 1); // whether worker is in Z		Vector<bool> inZ(W + 1); // whether worker is in Z
	while (job[wCur] != -1) { // runs at most jCur + 1 times		while (job[wCur] != -1) { // runs at most jCur + 1 times
	~~in_Z~~[wCur] = true;		inZ[wCur] = true;
	const int j = job[wCur];		const int j = job[wCur];
	T delta = inf;		T delta = inf;
Line 205:		Line 212:
	if (ckmin(minTo[w], C[j][w] - ys[j] - yt[w]))		if (ckmin(minTo[w], C[j][w] - ys[j] - yt[w]))
	prv[w] = wCur;		prv[w] = wCur;
	if (ckmin(delta, minTo[w])) ~~wNext = w;~~		if (ckmin(delta, minTo[w]))
			wNext = w;
	}		}
	}		}
Line 230:		Line 238:

	/**		/**
			* @brief Performs a sanity check for the Hungarian algorithm.
			*
	* Sanity check: https://en.wikipedia.org/wiki/Hungarian_algorithm#Example		* Sanity check: https://en.wikipedia.org/wiki/Hungarian_algorithm#Example
	* First job (5):		* First job (5):
Line 243:		Line 253:
	void sanityCheckHungarian() {		void sanityCheckHungarian() {
	Vector<Vector<int>> costs{{8, 5, 9}, {4, 2, 4}, {7, 3, 8}};		Vector<Vector<int>> costs{{8, 5, 9}, {4, 2, 4}, {7, 3, 8}};
	assert((hungarian(costs) == ~~vector~~<int>{5, 9, 15}));		assert((hungarian(costs) == Vector<int>{5, 9, 15}));
	std::println(stderr, "Sanity check passed.");		std::println(stderr, "Sanity check passed.");
	}		}

			/**
	// solves https://open.kattis.com/problems/cordonbleu		* @brief solves https://open.kattis.com/problems/cordonbleu
			*/
	void cordonBleu() {		void cordonBleu() {
	int N;		int N;
Line 275:		Line 287:
	}		}

			/**
			* @brief Entry point into the program.
			*
			* @return The return code of the program.
			*/
	int main() {		int main() {
	sanityCheckHungarian();		sanityCheckHungarian();

216.181.201.183: /* Implementation in C++ */

2025-04-20T15:09:41Z

Implementation in C++

← Previous revision		Revision as of 15:09, 20 April 2025
Line 160:		Line 160:
	*/		*/
	template <typename T>		template <typename T>
	bool ckmin(T& a, const T& b) {		constexpr bool ckmin(T& a, const T& b) {
	return b < a ? a = b, 1 : 0;		return b < a ? a = b, 1 : 0;
	}		}

216.181.201.183: /* Implementation in C++ */

2025-04-20T15:08:39Z

Implementation in C++

Show changes

Nabijaczleweli: fix link to Strongly-polynomial time

2025-03-28T00:11:35Z

fix link to Strongly-polynomial time

← Previous revision		Revision as of 00:11, 28 March 2025
Line 2:		Line 2:
	The '''Hungarian method''' is a [[combinatorial optimization]] [[algorithm]] that solves the [[assignment problem]] in [[polynomial time]] and which anticipated later [[Duality (optimization)\|primal–dual methods]]. It was developed and published in 1955 by [[Harold Kuhn]], who gave it the name "Hungarian method" because the algorithm was largely based on the earlier works of two Hungarian mathematicians, [[Dénes Kőnig]] and [[Jenő Egerváry]].<ref name="kuhn1955">Harold W. Kuhn, "The Hungarian Method for the assignment problem", ''[[Naval Research Logistics Quarterly]]'', '''2''': 83–97, 1955. Kuhn's original publication.</ref><ref name="kuhn1956">Harold W. Kuhn, "Variants of the Hungarian method for assignment problems", ''Naval Research Logistics Quarterly'', '''3''': 253–258, 1956.</ref> However, in 2006 it was discovered that [[Carl Gustav Jacobi]] had solved the assignment problem in the 19th century, and the solution had been published posthumously in 1890 in Latin.<ref>{{Cite web\|url=http://www.lix.polytechnique.fr/~ollivier/JACOBI/presentationlEngl.htm\|archive-url = https://web.archive.org/web/20151016182619/http://www.lix.polytechnique.fr/~ollivier/JACOBI/presentationlEngl.htm\|archive-date = 16 October 2015\|title = Presentation}}</ref>		The '''Hungarian method''' is a [[combinatorial optimization]] [[algorithm]] that solves the [[assignment problem]] in [[polynomial time]] and which anticipated later [[Duality (optimization)\|primal–dual methods]]. It was developed and published in 1955 by [[Harold Kuhn]], who gave it the name "Hungarian method" because the algorithm was largely based on the earlier works of two Hungarian mathematicians, [[Dénes Kőnig]] and [[Jenő Egerváry]].<ref name="kuhn1955">Harold W. Kuhn, "The Hungarian Method for the assignment problem", ''[[Naval Research Logistics Quarterly]]'', '''2''': 83–97, 1955. Kuhn's original publication.</ref><ref name="kuhn1956">Harold W. Kuhn, "Variants of the Hungarian method for assignment problems", ''Naval Research Logistics Quarterly'', '''3''': 253–258, 1956.</ref> However, in 2006 it was discovered that [[Carl Gustav Jacobi]] had solved the assignment problem in the 19th century, and the solution had been published posthumously in 1890 in Latin.<ref>{{Cite web\|url=http://www.lix.polytechnique.fr/~ollivier/JACOBI/presentationlEngl.htm\|archive-url = https://web.archive.org/web/20151016182619/http://www.lix.polytechnique.fr/~ollivier/JACOBI/presentationlEngl.htm\|archive-date = 16 October 2015\|title = Presentation}}</ref>

	[[James Munkres]] reviewed the algorithm in 1957 and observed that it is [[~~Time complexity#~~Strongly ~~and weakly~~ polynomial time\|(strongly) polynomial]].<ref name="munkres">J. Munkres, "Algorithms for the Assignment and Transportation Problems", ''[[Journal of the Society for Industrial and Applied Mathematics]]'', '''5'''(1):32–38, 1957 March.</ref> Since then the algorithm has been known also as the '''Kuhn–Munkres algorithm''' or '''Munkres assignment algorithm'''. The [[Computational complexity theory#Time and space complexity\|time complexity]] of the original algorithm was <math>O(n^4)</math>, however [[Jack Edmonds\|Edmonds]] and [[Richard Karp\|Karp]], and independently Tomizawa, noticed that it can be modified to achieve an <math>O(n^3)</math> running time.<ref>{{Cite journal\|last1=Edmonds\|first1=Jack\|last2=Karp\|first2=Richard M.\|date=1972-04-01\|title=Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems\|journal=Journal of the ACM\|volume=19\|issue=2\|pages=248–264\|language=EN\|doi=10.1145/321694.321699\|s2cid=6375478\|doi-access=free}}</ref><ref>{{Cite journal\|last=Tomizawa\|first=N.\|date=1971\|title=On some techniques useful for solution of transportation network problems\|journal=Networks\|language=en\|volume=1\|issue=2\|pages=173–194\|doi=10.1002/net.3230010206\|issn=1097-0037}}</ref> [[L. R. Ford, Jr.\|Ford]] and [[D. R. Fulkerson\|Fulkerson]] extended the method to general maximum flow problems in form of the [[Ford–Fulkerson algorithm]].		[[James Munkres]] reviewed the algorithm in 1957 and observed that it is [[Strongly-polynomial time\|(strongly) polynomial]].<ref name="munkres">J. Munkres, "Algorithms for the Assignment and Transportation Problems", ''[[Journal of the Society for Industrial and Applied Mathematics]]'', '''5'''(1):32–38, 1957 March.</ref> Since then the algorithm has been known also as the '''Kuhn–Munkres algorithm''' or '''Munkres assignment algorithm'''. The [[Computational complexity theory#Time and space complexity\|time complexity]] of the original algorithm was <math>O(n^4)</math>, however [[Jack Edmonds\|Edmonds]] and [[Richard Karp\|Karp]], and independently Tomizawa, noticed that it can be modified to achieve an <math>O(n^3)</math> running time.<ref>{{Cite journal\|last1=Edmonds\|first1=Jack\|last2=Karp\|first2=Richard M.\|date=1972-04-01\|title=Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems\|journal=Journal of the ACM\|volume=19\|issue=2\|pages=248–264\|language=EN\|doi=10.1145/321694.321699\|s2cid=6375478\|doi-access=free}}</ref><ref>{{Cite journal\|last=Tomizawa\|first=N.\|date=1971\|title=On some techniques useful for solution of transportation network problems\|journal=Networks\|language=en\|volume=1\|issue=2\|pages=173–194\|doi=10.1002/net.3230010206\|issn=1097-0037}}</ref> [[L. R. Ford, Jr.\|Ford]] and [[D. R. Fulkerson\|Fulkerson]] extended the method to general maximum flow problems in form of the [[Ford–Fulkerson algorithm]].

	==The problem==		==The problem==