I'm trying to learn how the cost minimising Hungarian Algorithm works on bipartite graphs. I can perform the algorithm on the adjacency matrix, but I want to understand how it works on graphs. I followed the worked example on Brilliant (https://brilliant.org/wiki/hungarian-matching/) and I think it's all fine. But both the proof of "A feasible labeling on a perfect match returns a maximum-weighted matching." and the example are for a maximum-weight matching, which is great if I want to maximise profit or something. But what if I need to have a minmium-weight for cost?
I'm not sure where to start. The triangle inequality still has to hold (?) so how can we use it to find a lower bound, instead of an upper bound? Do what we consider a feasible labelling and, hence, the equality graphs both have to change to the "opposite" as well? (It seems that the initial feasible labelling is already set for finding a maximum). I'm so confused. Any help would be appreciated.