I had a problem where I need to apply bipartite weighted matching on a graph where the edge weights are real (positive and negative). I have looked at several implementations of the Hungarian method but all of them expect a cost matrix of non-negative integers as input.
Moreover, I even looked at the pseudo code given in Figure 11-2 of Combinatorial Optimization: Algorithms and Complexity by Papadimitriou & Steiglitz. Even there, the pseudo code expects as input, cost matrix of non-negative integers. From what I understand of the algorithm, there shouldn't be any such restriction. Am I missing something here?