structural:scholar_edition
The algorithm in terms of bipartite graphs

Let us call a function y: (S ∪ T) → R {\displaystyle y:(S\cup T)\to \mathbb {R} } a potential if y (i) + y (j) ≤ c (i, j) {\displaystyle y(i)+y(j)\leq c(i,j)} for each i ∈ S, j ∈ T {\displaystyle i\in S,j\in T}. The value of potential y is the sum of the potential over all vertices: ∑ v ∈ S ∪ T y (v) {\displaystyle \sum _{v\in S\cup T}y(v)}.

The cost of each perfect matching is at least the value of each potential: the total cost of the matching is the sum of costs of all edges; the cost of each edge is at least the sum of potentials of its endpoints; since the matching is perfect, each vertex is an endpoint of exactly one edge; hence the total cost is at least the total potential.

The Hungarian method finds a perfect matching and a potential such that the matching cost equals the potential value. This proves that both of them are optimal. In fact, the Hungarian method finds a perfect matching of tight edges: an edge i j {\displaystyle ij} is called tight for a potential y if y (i) + y (j) = c (i, j) {\displaystyle y(i)+y(j)=c(i,j)}. Let us denote the subgraph of tight edges by G y {\displaystyle G_{y}}. The cost of a perfect matching in G y {\displaystyle G_{y}} (if there is one) equals the value of y.

During the algorithm we maintain a potential y and an orientation of G y {\displaystyle G_{y}} (denoted by G y → {\displaystyle {\overrightarrow {G_{y}}}}) which has the property that the edges oriented from T to S form a matching M. Initially, y is 0 everywhere, and all edges are oriented from S to T (so M is empty). In each step, either we modify y so that its value increases, or modify the orientation to obtain a matching with more edges. We maintain the invariant that all the edges of M are tight. We are done if M is a perfect matching.

In a general step, let R S ⊆ S {\displaystyle R_{S}\subseteq S} and R T ⊆ T {\displaystyle R_{T}\subseteq T} be the vertices not covered by M (so R S {\displaystyle R_{S}} consists of the vertices in S with no incoming edge and R T {\displaystyle R_{T}} consists of the vertices in T with no outgoing edge). Let Z be the set of vertices reachable in G y → {\displaystyle {\overrightarrow {G_{y}}}} from R S {\displaystyle R_{S}} by a directed path. This can be computed by breadth-first search.

If R T ∩ Z {\displaystyle R_{T}\cap Z} is nonempty, then reverse the orientation of all edges along a directed path in G y → {\displaystyle {\overrightarrow {G_{y}}}} from R S {\displaystyle R_{S}} to R T {\displaystyle R_{T}}. Thus the size of the corresponding matching increases by 1.

If R T ∩ Z {\displaystyle R_{T}\cap Z} is empty, then let

Δ is well defined because at least one such edge i j {\displaystyle ij} must exist whenever the matching is not yet of maximum possible size (see the following section); it is positive because there are no tight edges between Z ∩ S {\displaystyle Z\cap S} and T ∖ Z {\displaystyle T\setminus Z}. Increase y by Δ on the vertices of Z ∩ S {\displaystyle Z\cap S} and decrease y by Δ on the vertices of Z ∩ T {\displaystyle Z\cap T}. The resulting y is still a potential, and although the graph G y {\displaystyle G_{y}} changes, it still contains M (see the next subsections). We orient the new edges from S to T. By the definition of Δ the set Z of vertices reachable from R S {\displaystyle R_{S}} increases (note that the number of tight edges does not necessarily increase).

We repeat these steps until M is a perfect matching, in which case it gives a minimum cost assignment. The running time of this version of the method is O (n 4) {\displaystyle O(n^{4})}: M is augmented n times, and in a phase where M is unchanged, there are at most n potential changes (since Z increases every time). The time sufficient for a potential change is O (n 2) {\displaystyle O(n^{2})}.